Submission #784310

#	Time	Username	Problem	Language	Result	Execution time	Memory
784310		Trunkty	Trampoline (info1cup20_trampoline)	C++14	100 / 100	1078 ms	98684 KiB

trampoline

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll

int r,c,n,t;
map<int,set<int>> mp;
map<pair<int,int>,int> pos;
map<int,pair<int,int>> rev;
int nextpos=1;
int jump[200005][21];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> r >> c >> n;
    for(int i=1;i<=n;i++){
        int a,b;
        cin >> a >> b;
        mp[a].insert(b);
    }
    for(auto it=mp.begin();it!=mp.end();it++){
        int x = it->first;
        set<int> s = it->second;
        for(int y:s){
            pos[{x,y}] = nextpos;
            rev[nextpos] = {x,y};
            nextpos++;
        }
    }
    for(auto it=mp.begin();it!=mp.end();it++){
        int x = it->first;
        set<int> s = it->second;
        for(int y:s){
            auto it = mp[x+1].lower_bound(y);
            if(it!=mp[x+1].end()){
                jump[pos[{x,y}]][0] = pos[{x+1,(*it)}];
            }
        }
    }
    for(int j=1;j<=20;j++){
        for(int i=1;i<=n;i++){
            jump[i][j] = jump[jump[i][j-1]][j-1];
        }
    }
    cin >> t;
    for(int i=1;i<=t;i++){
        int x1,y1,x2,y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if(x1>x2){
            cout << "No" << "\n";
        }
        else if(x1==x2){
            if(y1<=y2){
                cout << "Yes" << "\n";
            }
            else{
                cout << "No" << "\n";
            }
        }
        else{
            auto it = mp[x1].lower_bound(y1);
            if(it==mp[x1].end()){
                cout << "No" << "\n";
                continue;
            }
            int p = pos[{x1,(*it)}];
            for(int j=20;j>=0;j--){
                if(x1+(1<<j)<=x2-1){
                    x1 += (1<<j);
                    p = jump[p][j];
                }
            }
            if(p==0 or rev[p].second>y2){
                cout << "No" << "\n";
            }
            else{
                cout << "Yes" << "\n";
            }
        }
    }
    return 0;
}

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