Educational Codeforces Round 132 (Rated for Div. 2) D. Rorororobot

Educational Codeforces Round 132 (Rated for Div. 2) D. Rorororobot

What if there were no blocked cells? Then the movement is easy. From cell $(x,y)$ we can go to cells $(x+k,y),(x,y+k),(x-k,y)$ or $(x,y-k)$. Thus, we can visit all cells that have the same remainder modulo $k$ over both dimensions. The answer would be “YES” if $x_s$ mod $k=x_f$ mod $k$ and $y_s$ mod $k$ = $y_f$ mod $k$.

Let’s choose the following path from start to finish. Let xs be less or equal to xf. If that isn’t the case, swap the cells. First, move up until the row is the same, then move to the side until the column is the same.

What stops us from doing the same on a grid with blocked cells? The first part of the part can remain the same — we can always move up from the cell. Only cells below the start cell can be blocked. The second part is trickier. If there is a column with too many blocked cells between the start and the finish column, then we won’t be able to pass through it.

Let’s adjust the path for that. Move up as high as possible — to the highest cell with the same remainder modulo k in this column. Then move to the finish column and go down to the finish cell.

If there still exists a column with too many blocked cells, then the answer is “NO”. No matter what we do, we won’t be able to go around that column. Otherwise, the answer is “YES”.

Thus, the solution is to check for remainders, then find the largest number of blocked cells between the query columns and compare it to the highest row with the same remainder modulo k as the start or the finish. You can use any RMQ data structure you want.

Overall complexity: $O(nlogn+q)$ with sparse table for RMQ, for example.

#include
using namespace std;

const int N = 200010, M = 18;

int n,m;
int a[N],f[N][M];

void init()
{
    for(int j=0;j<M;j++)
        for(int i=1;i+(1<<j)-1<=m;i++)
            if(!j) f[i][j]=a[i];
            else f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}

int query(int l, int r)
{
    int len=r-l+1;
    int k=log(len)/log(2);
    return max(f[l][k],f[r-(1<<k)+1][k]);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>a[i];

    init();

    int q;cin>>q;
    while(q--)
    {
        int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;
        int k;cin>>k;

        if(y1>y2)
        {
            swap(x1,x2);
            swap(y1,y2);
        }

        bool ok=1;
        if(abs(x1-x2)%k!=0 || abs(y1-y2)%k!=0) ok=0;
        int h=query(y1,y2);

        if(h>=x1)
        {
            int d=h-x1+1;
            int dist=(d+k-1)/k*k+x1;
            if(dist>n) ok=0;
        }

        if(ok) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61