제출 #1347779

#제출 시각아이디문제언어결과실행 시간메모리
1347779ChocoTrampoline (info1cup20_trampoline)C++20
0 / 100
985 ms99924 KiB
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#define ll long long
#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=1e18;
ll mod=1e9+7;
ll add=5e5;
void work(){
    ll r,c,n;
    cin>>r>>c>>n;
    set<ll>rows;
    vector<pair<ll,ll>>green(n+10);
    map<pair<ll,ll>,ll>ind;
    fori(i,1,n){
        cin>>green[i].ff>>green[i].ss;
        rows.ins(green[i].ff);
        ind[green[i]]=i;
    }
    ll t;
    cin>>t;
    vector<pair<pair<ll,ll>,pair<ll,ll>>>qu(t+10);
    fori(i,1,t){
        cin>>qu[i].ff.ff>>qu[i].ff.ss>>qu[i].ss.ff>>qu[i].ss.ss;
    }
    map<ll,set<ll>>gr;
    fori(i,1,n){
        gr[green[i].ff].ins(green[i].ss);
    }
    vector<vector<ll>>lca(n+10,vector<ll>(30,-1));
    for(auto i: rows){
        for(auto x: gr[i]){
            if(gr.find(i-1)==gr.end())
            break;
            auto it=gr[i-1].upper_bound(x);
            if(it==gr[i-1].begin())
            continue;
            it--;
            pair<ll,ll>p={i,x};
            ll ind1=ind[p];
            p={i-1,*it};
            ll ind2=ind[p];
            lca[ind1][0]=ind2;
            fori(j,1,30){
                if(lca[ind1][j-1]==-1)
                break;
                lca[ind1][j]=lca[lca[ind1][j-1]][j-1];
            }
        }
    }
    vector<ll>ans(t+10,0);
    fori(i,1,t){
        ll sr=qu[i].ff.ff,sc=qu[i].ff.ss;
        ll er=qu[i].ss.ff,ec=qu[i].ss.ss;
        if(sr==er and sc<=ec){
            ans[i]=1;
            continue;
        }
        if(gr[sr].size()==0 || gr[er-1].size()==0)
        continue;
        auto it=gr[sr].lower_bound(sc);
        if(it==gr[sr].end())
        continue;
        pair<ll,ll>p={sr,*it};
        ll ind1=ind[p];
        it=gr[er-1].upper_bound(ec);
        if(it==gr[er-1].begin())
        continue;
        it--;
        p={er-1,*it};
        ll ind2=ind[p];
        for(ll j=29;j>=0;j--){
            if(lca[ind2][j]==-1 || green[lca[ind2][j]].ff>green[ind1].ff)
            continue;
            ind2=lca[ind2][j];
            //cout<<ind2<<endl;
        }
        if(green[ind2].ff==green[ind1].ff and green[ind1].ss<=green[ind2].ss){
            ans[i]=1;
        }
    }
    fori(i,1,t)
    if(ans[i])
    cout<<"Yes\n";
    else
    cout<<"No\n";
}
int main()
{
    //#ifndef LOCAL
    // freopen("log1.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...