제출 #493827

#제출 시각아이디문제언어결과실행 시간메모리
493827SirCovidThe19thTrampoline (info1cup20_trampoline)C++17
11 / 100
1207 ms63232 KiB
#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[c + 1].upper_bound({r, 1e9});
            if (it != mp[c + 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){ 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";
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...