Submission #1314206

#TimeUsernameProblemLanguageResultExecution timeMemory
1314206ulvixTrampoline (info1cup20_trampoline)C++20
54 / 100
479 ms47216 KiB
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#ifdef ULVI
    #include "debug.hpp"
#else
    #define db(...)
    #define dbv(v)
    #define line()
#endif
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define ff first
#define ss second
#define enld endl
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll sz=2e5+100;
const ll lg=20;
const ll mod=1e9+7;
const ll inf=1e18;
template<class T>
using indexed_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
void solve(){
    ll r,c,n,q;
    cin>>r>>c>>n;
    vector<pll> v(n+5);
    for(ll i=1;i<=n;i++) cin>>v[i].ff>>v[i].ss;
    vector<vector<ll>> up(lg,vector<ll>(n+5));
    map<ll,vector<pll>> mp;
    for(ll i=1;i<=n;i++) mp[v[i].ff].push_back({v[i].ss,i});
    for(auto &[x,a]:mp) sort(all(a));
    for(ll i=1;i<=n;i++){
        auto [x,y]=v[i];
        if(!mp.count(x+1)) continue;
        auto it=lower_bound(all(mp[x+1]),make_pair(y,-1ll));
        if(it!=mp[x+1].end()) up[0][i]=(*it).ss;
    }
    for(ll i=1;i<lg;i++){
        for(ll j=1;j<=n;j++) up[i][j]=up[i-1][up[i-1][j]];
    }
    cin>>q;
    while(q--){
        ll x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        if(x1==x2){
            cout<<"Yes\n";
            continue;
        }
        auto it=lower_bound(all(mp[x1]),make_pair(y1,-1ll));
        if(it==mp[x1].end()){
            cout<<"No\n";
            continue;
        }
        ll idx=(*it).ss;
        ll d=x2-x1-1;
        for(ll i=0;i<lg;i++) if(d>>i&1) idx=up[i][idx];
        if(idx && v[idx].ss<=y2) cout<<"Yes\n";
        else cout<<"No\n";
    }
}

int main(){
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t=1;
    // cin>>t;
    for(ll _=1;_<=t;_++){
        // cout<<"Scenario #"<<_<<":\n";
        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...