Submission #1124553

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124553		yusufhocaoglu	Trampoline (info1cup20_trampoline)	C++20	100 / 100	823 ms	26240 KiB

trampoline

#include <bits/stdc++.h>
#define vi vector<int>
#define pri pair<int,int>
using namespace std;

int main() {
    int r,c,n;cin>>r>>c>>n;
    vector<pri> green(n);
    for (int i = 0;i<n;i++) {
        int a,b;
        cin>>a>>b;
        green[i] = pri{a,b};
    }
    sort(green.begin(),green.end());
    int l = 1;
    vector<vi> go(n,vi(20));
    for (int i = 0;i<n;i++) {
        //cout<<green[i].first<<" "<<green[i].second<<endl;
        while (l<green.size() && (green[l].first <= green[i].first || (green[i].first+1 == green[l].first && green[l].second<green[i].second))) l++;
        go[i][0] = l;
        if (l==n || green[l].first!=green[i].first+1) go[i][0] = -1;
        
    }
    for (int i = 1;i<20;i++) {
        for (int j = 0;j<n;j++) {
            if (go[j][i-1]==-1) {
                go[j][i] = -1;continue;
            }
            go[j][i] = go[go[j][i-1]][i-1];
        }
    }
    int q;cin>>q;
    while (q--) {
        int rs,cs,re,ce;cin>>rs>>cs>>re>>ce;
        if (rs>re || cs>ce) {
            cout<<"No"<<endl;continue;
        }
        if (rs==re) {
            cout<<"Yes"<<endl;continue;
        }
        auto it = lower_bound(green.begin(),green.end(),pri{rs,cs});
        if (it==green.end() || it->first != rs) {
            cout<<"No"<<endl;continue;
        }
        auto i =  it-green.begin();
        // go re-rs rows from i
        int dist = re-rs-1;
        int l = 0;
        while (i!=-1 && dist!=0) {
            if (dist&1) i=go[i][l];
            l++;
            dist>>=1;
        }
        if (i==-1 || green[i].second > ce) {
            cout<<"No"<<endl;continue;
        } cout<<"Yes"<<endl;
    }
}

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