oj.uz

Submission #522733

# Submission time Handle Problem Language Result Execution time Memory
522733 2022-02-05T15:02:11 Z alexdumitru Trampoline (info1cup20_trampoline) C++14
0 / 100
 2000 ms 2500 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2076 ms 324 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2071 ms 2500 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2080 ms 1760 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2023 ms 580 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2058 ms 2440 KB Time limit exceeded
2 Halted 0 ms 0 KB -