Submission #522706

#	Time	Username	Problem	Language	Result	Execution time	Memory
522706		alexdumitru	Trampoline (info1cup20_trampoline)	C++14	0 / 100	325 ms	18900 KiB

trampoline

#include <bits/stdc++.h>

using namespace std;
pair<int,int> a[200005];
int n,i,t,j,l2[200005],sx,sy,fx,fy,r,c,lift[200005][20],pu[25];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>r>>c>>n;
    for(i=1;i<=n;i++)
    {
        cin>>a[i].first>>a[i].second;
        if(i>1)
            l2[i]=l2[i>>1]+1;
    }
    sort(a+1,a+n+1);
    pu[0]=1;
    for(i=1;i<20;i++)
        pu[i]=pu[i-1]<<1;
    for(i=1;i<=n;i++)
    {
        int st=i+1;
        int dr=n;
        int poz=0;
        while(st<=dr)
        {
            int m=(st+dr)/2;
            if(a[m].first==a[i].first)
                st=m+1;
            else {
                if(a[m].first-a[i].first>1)
                    dr=m-1;
                else {
                    if(a[m].second>=a[i].second)
                    {
                        poz=m;
                        dr=m-1;
                    }
                    else st=m+1;
                }
            }
        }
        if(a[poz].first-a[i].first==1)
            lift[i][0]=poz;
    }
    for(j=1;j<=l2[n];j++)
        for(i=1;i<=n;i++)
            lift[i][j]=lift[lift[i][j-1]][j-1];
    cin>>t;
    while(t--)
    {
        cin>>sx>>sy>>fx>>fy;
        if(sx<1||fx<1||sy<1||fy<1||sx>r||fx>r||sy>c||fy>c)
        {
            cout<<"No\n";
            continue;
        }
        if(sx>fx)
        {
            cout<<"No\n";
        }
        else if(sx==fx)
        {
            cout<<"Yes\n";
        }
        else {
            if(sy>fy)
            {
                cout<<"No\n";
                continue;
            }
            int k=0;
            int st=1;
            int dr=n;
            int poz=0;
            while(st<=dr)
            {
                int m=(st+dr)/2;
                if(a[m].first<sx)
                    st=m+1;
                else if(a[m].first>sx)
                    dr=m-1;
                else {
                    if(a[m].second>=sy)
                    {
                        poz=m;
                        dr=m-1;
                    }
                    else st=m+1;
                }
            }
            k=poz;
            if(!k||a[k].second>fy)
            {
                cout<<"No\n";
                continue;
            }
            for(j=l2[n];j>=0;j--)
            {
                pair<int,int> x = a[lift[k][j]];
                if(1&&x.first<fx)
                {
                    k=lift[k][j];
                }
                else if(1&&x.first==fx)
                {
                    k=lift[k][j];
                    break;
                }
            }
            if(a[k].first>=fx-1&&a[k].second<=fy)
                cout<<"Yes\n";
            else cout<<"No\n";
        }
    }
    return 0;
}

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