Submission #1317162

#TimeUsernameProblemLanguageResultExecution timeMemory
1317162hssaan_arifTrampoline (info1cup20_trampoline)C++20
100 / 100
266 ms35644 KiB
// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
using namespace std;

#define endl "\n"
#define pb push_back
#define int long long
#define fi first
#define se second
#define pii pair<int,int>

const int N = 3e5 + 5, M = 1e9 + 7, LG = 20;

int n , r , c ,  sp[N][LG] , q , x , y , a , b;
pii A[N];

void solve(){
    cin >> r >> c >> n;

    for (int i=0 ; i<n ; i++){
        cin >> A[i].fi >> A[i].se;
    }

    int j=1;
    sort(A,A+n);

    for (int i=0 ; i<n ; i++){
        while(j < n && A[j] < pii(A[i].fi+1 , A[i].se)){
            j++;
        }

        if (A[j].fi == A[i].fi + 1){
            sp[i][0] = j;
        }else{
            sp[i][0] = n;
        }
    }
    sp[n][0] = n;

    for (int j=1 ; j<LG ; j++){
        for (int i=0 ; i<=n ; i++){
            sp[i][j] = sp[sp[i][j-1]][j-1];
        }
    }

    cin >> q;

    while(q--){
        cin >> x >> y >> a >> b;

        if (a < x || b < y){
            cout << "NO" << endl;
            continue;
        }

        if (a==x){
            cout << "YES" << endl;
            continue;
        }

        int nx = lower_bound(A,A+n,pii(x,y)) - A;

        if (A[nx].fi != x){
            cout << "NO" << endl;
            continue;
        }

        for (int i=LG-1 ; i>=0 ; i--){
            if (x + (1<<i) < a){
                x += (1<<i);
                nx = sp[nx][i];
            }
        }

        // cout << nx << endl;

        if (nx == n){
            cout << "NO" << endl;
            continue;
        }

        if (A[nx].se <= b){
            cout << "YES" << endl;
        }else{
            cout << "NO" << endl;
        }

    }


}

signed main(){
    // freopen("" , "r" , stdin);
    // freopen("" , "w" , stdout);
    // cout << setprecision(30);
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int ts = 1;
    // cin >> ts;
    while(ts--){
        solve();
    }
}
#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...