제출 #1348934

#제출 시각아이디문제언어결과실행 시간메모리
1348934ChocoTrampoline (info1cup20_trampoline)C++20
23 / 100
2096 ms37968 KiB
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#define ll int
#define fori(i,j,k) for(ll i=j; i<=k;i++)
#define study ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define pb push_back
#define all(s) s.begin(),s.end()
#define ins insert
#define ss second
#define ff first
#ifndef DB
#define DB 0
#endif
#define debugl(l) if constexpr((l)<DB)
#define debug debugl(0)
const ll sz=1e6+10;
ll INF=0x3F3F3F3F;
ll mod=1e9+7;
ll add=5e5;
void work(){
    ll r,c,n;
    cin>>r>>c>>n;
    vector<pair<ll,ll>>cells(n);
    set<ll>avb;
    fori(i,0,n-1){
        cin>>cells[i].ff>>cells[i].ss;
        avb.ins(cells[i].ff); avb.ins(cells[i].ff+1);
    }
    sort(all(cells));
    vector<vector<array<ll,2>>>gr(avb.size());
    vector<vector<ll>>lca(n,vector<ll>(30,-1));
    fori(i,0,n-1){
        ll it=distance(avb.begin(),avb.lower_bound(cells[i].ff));
        gr[it].pb({cells[i].ss,i});
    }
    auto getnext = [&](ll x,ll y){
        if(x>=avb.size()) return -1;
        auto it=lower_bound(all(gr[x]),array<ll,2>{y,-1});
        if(it==gr[x].end()) return -1;
        return (*it)[1];
    };
    fori(i,0,n-1){
        ll it=distance(avb.begin(),avb.lower_bound((cells[i].ff)));
        it++;
        ll p=getnext(it,cells[i].ss);
        lca[i][0]=p;
    }
    fori(j,1,29){
        fori(i,0,n-1){
            if(lca[i][j-1]==-1)
            continue;
            lca[i][j]=lca[lca[i][j-1]][j-1];
        }
    }
    ll t;
    cin>>t;
    fori(i,0,t-1){
        ll x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        if(y1>y2)
        cout<<"No\n";
        else if(x1==x2)
        cout<<"Yes\n";
        else if(!avb.count(x1) || !avb.count(x2) || x2<x1){
            cout<<"No\n";
        }
        else{
            x1=distance(avb.begin(),avb.lower_bound(x1));
            x2=distance(avb.begin(),avb.lower_bound(x2));
            ll st=getnext(x1,y1);
            for(int i=29; st!=-1 and i>=0;i--){
                int ahs=distance(avb.begin(),(avb.lower_bound(cells[st].ff)));
                if((x2-1-ahs)& (1<<i)){
                    debug{
                        cout<<st<<" "<<i<<endl;
                    }
                    st=lca[st][i];
                }
            }
            if(st==-1 || cells[st].ss>y2) cout<<"No\n";
            else
            cout<<"Yes\n";
        }
    }
}
int main()
{
    //#ifndef LOCAL
    //freopen("log.txt","r",stdin);
    // freopen("log2.txt","w",stdout);
    //#endif
    study;
    ll t=1;
    //cin>>t;
    fori(i,1,t){
        work();
    }
}
#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...