Submission #208513

#	Time	Username	Problem	Language	Result	Execution time	Memory
208513		Alexa2001	Trampoline (info1cup20_trampoline)	C++17	100 / 100	402 ms	20088 KiB

trampoline

#include <bits/stdc++.h>

using namespace std;

/* Problem: Trampoline
 * Complexity: O(NlogN + TlogN)
 * Score: 100
 */ 

const int Nmax = 2e5 + 5, lg = 20, lim = 1e9;

int n, m, p;
int father[lg+2][Nmax], Next[Nmax];

pair<int,int> a[Nmax];

int nr_yes, nr_no, cVal;


void answer_yes(int x)
{
    cout << "Yes\n";
}

void answer_no(int x)
{
    cout << "No\n";
}

void Read()
{
    assert( cin >> n >> m >> p );
    assert( n <= lim && m <= lim && p <= 200000);

    int i;
    for(i=1; i<=p; ++i)
        cin >> a[i].first >> a[i].second;

    sort(a+1, a+p+1);
}

int BinarySearch(pair<int,int> w)
{
    int l = 1, r = p, mid;

    while(l <= r)
    {
        mid = (l + r) / 2;
        if(a[mid] < w) l = mid + 1;
        else r = mid - 1;
    }
    return l;
}

void ComputeNext()
{
    int i;
    for(i=1; i<=p; ++i)
    {
        int id = BinarySearch({ a[i].first + 1, a[i].second });

        if(id > p || a[id].first != a[i].first + 1)
            Next[i] = 0;
        else Next[i] = id;
    }
}

void ComputeAncestors()
{
    int i, j;

    for(i=1; i<=p; ++i)
        father[0][i] = Next[i];

    for(i=1; i<=lg; ++i)
        for(j=1; j<=p; ++j)
            father[i][j] = father[i-1][father[i-1][j]];
}

int FindMyAncestor(int node, int up)
{
    int i;
    for(i=0; i<=lg; ++i)
        if(up & (1<<i))
        {
            node = father[i][node];
            if(!node) return 0;
        }
    return node;
}

void SolveQueries()
{
    int q;
    assert( cin >> q );
    assert ( q <= 200000 );

    int i;
    for(i=1; i<=q; ++i)
    {
        int X1, Y1, X2, Y2;
        assert( cin >> X1 >> Y1 >> X2 >> Y2 );       
        assert( 1 <= X1 && 1 <= X2 && 1 <= Y1 && 1 <= Y2 && X1 <= lim && X2 <= lim && Y1 <= lim && Y2 <= lim);

        if(make_pair(X1, Y1) > make_pair(X2, Y2))
        {
            answer_no(i);
            continue;
        }

        if(X1 == X2)
        {
            answer_yes(i);
            continue;
        }

        int id = BinarySearch({X1, Y1});
        if(id > p || a[id].first != X1)
        {
            answer_no(i);
            continue;
        }

        int w = FindMyAncestor(id, X2 - X1 - 1);

        if(w == 0)
        {
            answer_no(i);
            continue;
        }

        if(a[w].second <= Y2)
           answer_yes(i);
        else answer_no(i);
    }
}

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

    Read();
    ComputeNext();
    ComputeAncestors();
    SolveQueries();

    return 0;
}

• Subtask 1: 23 / 23
• Subtask 2: 20 / 20
• Subtask 3: 11 / 11
• Subtask 4: 19 / 19
• Subtask 5: 27 / 27