Submission #493831

#	Time	Username	Problem	Language	Result	Execution time	Memory
493831		SirCovidThe19th	Trampoline (info1cup20_trampoline)	C++17	100 / 100	1314 ms	55836 KiB

trampoline

#include <bits/stdc++.h>
using namespace std; 
 
#define FOR(i, x, y) for (int i = x; i < y; i++)
 
const int mx = 2e5 + 5, ml = 18;
 
int R, C, n, q, col[mx], down[mx][ml]; map<int, set<pair<int, int>>> mp; 
 
int main(){
    cin >> R >> C >> n;
    FOR(i, 1, n + 1){
        int r, c; cin >> r >> c;
        col[i] = c;
        mp[r].insert({c, i});
    }
    for (auto [r, S] : mp)
        for (auto [c, idx] : S){
            auto it = mp[r + 1].lower_bound({c, -1});
            if (it != mp[r + 1].end()) down[idx][0] = it->second;
        }
    FOR(l, 1, ml) FOR(i, 1, n + 1) down[i][l] = down[down[i][l - 1]][l - 1];
 
    cin >> q;
    while (q--){
        int r1, c1, r2, c2; cin >> r1 >> c1 >> r2 >> c2;
        if (r1 > r2 or c1 > c2){ cout<<"No"<<"\n"; continue; }
        if (r1 == r2){ cout<<"Yes"<<"\n"; continue; }
 
        auto st = mp[r1].lower_bound({c1, -1});
        int cur = (st == mp[r1].end()) ? 0 : st->second;
        int jmp = r2 - r1 - 1;
 
        FOR(l, 0, ml) if ((jmp >> l) & 1) cur = down[cur][l];
        cout<<((!cur or col[cur] > c2) ? "No" : "Yes")<<"\n";
    }
}

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