Submission #522733

#	Time	Username	Problem	Language	Result	Execution time	Memory
522733		alexdumitru	Trampoline (info1cup20_trampoline)	C++14	0 / 100	2080 ms	2500 KiB

trampoline

#include <bits/stdc++.h>

using namespace std;
pair<int,int> a[200005];
int n,i,t,j,sx,sy,fx,fy,r,c,lift[200005][22];
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;
    sort(a+1,a+n+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+1)
                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=i-1;
                }
                else st=i-1;
            }
        }
        lift[i][0]=poz;
    }
    for(j=1;j<=20;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>fx)
        {
            cout<<"No\n";
        }
        else if(sx==fx)
        {
            if(sy<=fy)
                cout<<"Yes\n";
            else cout<<"No\n";
        }
        else {
            if(sy>fy)
            {
                cout<<"No\n";
                continue;
            }
            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)
                        st=m+1;
                    else {
                        dr=m-1;
                        poz=m;
                    }
                }
            }
            if(!poz)
            {
                cout<<"No\n";
                continue;
            }
            int di=fx-sx-1;
            for(j=0;j<=30;j++)
                if(di&(1<<j))
                    poz=lift[poz][j];
            if(a[poz].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