Jumping Around Codeforces Solution

Jumping Around Codeforces Solution

There is an infinite pond that can be represented with a number line. There are nn rocks in the pond, numbered from 11 to nn. The ii-th rock is located at an integer coordinate aiai. The coordinates of the rocks are pairwise distinct. The rocks are numbered in the increasing order of the coordinate, so a1<a2<⋯<ana1<a2<⋯<an.

A robot frog sits on the rock number ss. The frog is programmable. It has a base jumping distance parameter dd. There also is a setting for the jumping distance range. If the jumping distance range is set to some integer kk, then the frog can jump from some rock to any rock at a distance from d−kd−k to d+kd+k inclusive in any direction. The distance between two rocks is an absolute difference between their coordinates.

You are assigned a task to implement a feature for the frog. Given two integers ii and kk determine if the frog can reach a rock number ii from a rock number ss performing a sequence of jumps with the jumping distance range set to kk. The sequence can be arbitrarily long or empty.

You will be given qq testcases for that feature, the jj-th testcase consists of two integers ii and kk. Print “Yes” if the ii-th rock is reachable and “No” otherwise.

You can output “YES” and “NO” in any case (for example, strings “yEs”, “yes”, “Yes” and ‘YES”‘ will be recognized as a positive answer).Input

The first line contains four integers nn, qq, ss and dd (1≤n,q≤2⋅1051≤n,q≤2⋅105; 1≤s≤n1≤s≤n; 1≤d≤1061≤d≤106) — the number of rocks, the number of testcases, the starting rock and the base jumping distance parameter.

The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1061≤ai≤106) — the coordinates of the rocks. The coordinates of the rocks are pairwise distinct. The rocks are numbered in the increasing order of distance from the land, so a1<a2<⋯<ana1<a2<⋯<an.

Each of the next qq lines contains two integers ii and kk (1≤i≤n1≤i≤n; 1≤k≤1061≤k≤106) — the parameters to the testcase.Output

For each of the testcases print an answer. If there is a sequence of jumps from a rock number ss to a rock number ii with the jumping distance range set to kk, then print “Yes”. Otherwise, print “No”.

Examples

input

7 4 4 5
1 5 10 13 20 22 28
4 1
7 2
7 3
3 2

output

Yes
No
Yes
Yes

input

10 8 6 11
1 2 4 7 8 9 11 13 19 20
2 13
5 8
8 1
6 15
1 15
2 7
7 6
8 9

output

Yes
Yes
No
Yes
Yes
Yes
Yes
Yes

input

6 9 6 6
1 2 4 9 18 19
2 17
1 18
5 4
2 11
5 17
6 8
4 3
3 3
6 6

output

Yes
Yes
Yes
Yes
Yes
Yes
No
No
Yes

input

4 1 1 10
1 8 10 19
2 1

output

Yes

Note

Explanation of the first example:

In the first testcase the destination rock is the same as the starting rock, thus no jumps are required to reach it.

In the second testcase the frog can jump any distance in the range [5−2;5+2][5−2;5+2]. Thus, it can reach rock number 55 (by jumping 77 to the right) and rock number 33 (by jumping 33 to the left). From rock number 33 it can reach rock number 22 (by jumping 55 to the left). From rock number 22 it can reach rock number 11 (by jumping 44 to the left). However, there is no way to reach rock number 77.

In the third testcase the frog can jump any distance in the range [5−3;5+3][5−3;5+3]. Thus, it can reach rock number 77 by jumping to rock 55 first and to 77 afterwards.

The fourth testcase is shown in the explanation for the second testcase.

Solution

#include <bits/stdc++.h>
#define DBG if(0)
using namespace std;

int n,q,d,strock;
int li = 1<<22L;
int off = 1<<20L;
struct thing
{
    int l,r,v;
    bool hasrock=false;
};
vector<thing> s;
struct Q
{
    int idx,rock,k,ans;
};

bool byk(Q a,Q b)
{
    return a.k < b.k;
}

bool byidx(Q a,Q b)
{
    return a.idx < b.idx;
}

vector<int> jumpable;
stack<int> todo_rocks;

void S(int l,int r,int k)
{
    if(s[k].v==0) return;
    if(k >= li)
    {
        s[k].v = 0;
        jumpable.push_back(k);
        DBG cout << "hop " << k-li << "\n";
        if(s[k].hasrock) todo_rocks.push(k-li);
        return;
    }

    if(s[k*2].r < l) S(l,r,k*2+1);
    else if (s[k*2+1].l > r) S(l,r,k*2);
    else
    {
        S(l,s[k*2].r,k*2);
        S(s[k*2+1].l,r,k*2+1);
    }

    s[k].v = s[k*2].v + s[k*2+1].v;
}

void hladaj(int x,int k)
{
    DBG cout << "skacem z kamena " << x << "\n";
    pair<int,int> L = {x-d-k+li,x-d+k+li};
    pair<int,int> R = {x+d-k+li,x+d+k+li};

    L.first = max(L.first,li+3);
    L.second = min(L.second,li*2-5);
    R.first = max(R.first,li+3);
    R.second = min(R.second,li*2-5);

    S(L.first, L.second, 1);
    S(R.first, R.second, 1);
}

void bubli(int x)
{
    if(!x)return;
    s[x].v = s[x*2].v + s[x*2+1].v;
    bubli(x/2);
}

bool bad_x(int x)
{
    return (x==li) || (x==li*2-1);
}

unordered_set<int> update_edges(unordered_set<int> &edges)
{
    unordered_set<int> n_edges;

    for(int x : jumpable)
    {
        if(bad_x(x)) continue;
        for(int dx=-1;dx<=1;dx+=2)
        {
            int nx = x + dx;
            if(bad_x(nx)) continue;
            if(s[nx].v==0) continue;
            DBG cout << x-li << " jumpable, edge " << nx-li << "\n";
            n_edges.insert(nx);
        }
    }
    jumpable.clear();

    for(int x : edges)
    {
        if(bad_x(x)) continue;
        for(int dx=-1;dx<=1;dx+=2)
        {
            int nx = x + dx;
            if(bad_x(nx)) continue;
            if(s[nx].v==0) continue;
            DBG cout << x-li << " was edge, will be " << nx-li << "\n";
            n_edges.insert(nx);
        }
    }

    DBG
    {
        cout << "edges: ";
        for(int x : n_edges) cout << x-li << " ";
        cout << "\n";
    }

    return n_edges;
}

void solve(vector<int> &rocks, vector<Q> &qs)
{
    int idx = 0;

    todo_rocks.push(rocks[strock]);
    
    while(todo_rocks.size())
    {
        int v = todo_rocks.top();
        todo_rocks.pop();
        hladaj(v,0);
    }

    unordered_set<int> edges;
    edges = update_edges(edges);

    int cur_k = 0;

    for(int i=0;i<qs.size();++i)
    {
        while(cur_k != qs[i].k)
        {
            cur_k++;
            DBG cout << "k = " << cur_k << "\n";
            for(int x : edges)
            {
                if(s[x].v==0) continue;
                if(bad_x(x)) continue;

                DBG cout << "hopla " << x-li << "\n";
                s[x].v = 0;
                bubli(x/2);

                if(s[x].hasrock) todo_rocks.push(x-li);
            }

            while(todo_rocks.size())
            {
                int v = todo_rocks.top();
                todo_rocks.pop();
                hladaj(v,cur_k);
            }

            edges = update_edges(edges);

        }

        int x = rocks[ qs[i].rock ];
        qs[i].ans = (s[li+x].v == 0) || (qs[i].rock == strock);
        
    }

}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q >> strock >> d;
    --strock;

    vector<int> rocks(n);

    s.resize(li*2);

    for(int i=0;i<n;++i)
    {
        cin >> rocks[i];
        rocks[i] += off;
        s[li+rocks[i]].hasrock = true;
    }

    for(int i=li;i<li*2;++i)
    {
        s[i].v = 1;
        s[i].l = s[i].r = i;

    }

    for(int i=li-1;i>0;--i)
    {
        s[i].v = s[i*2].v + s[i*2+1].v;
        s[i].l = s[i*2].l;
        s[i].r = s[i*2+1].r;
    }

    vector<Q> qs(q);
    for(int i=0;i<q;++i)
    {
        qs[i].idx = i;
        cin >> qs[i].rock >> qs[i].k;
        qs[i].rock--;
    }

    Q tmp;
    tmp.idx = q+47;
    tmp.k = 0;
    tmp.rock = strock;

    qs.push_back(tmp);

    sort(qs.begin(),qs.end(),byk);

    solve(rocks, qs);

    sort(qs.begin(),qs.end(),byidx);
    for(int i=0;i<q;++i)
    {
        if(qs[i].ans) cout << "Yes\n";
        else cout << "No\n";
    }

    return 0;
}

Educational Codeforces Round 111 (Rated for Div. 2)

Leave a Comment