제출 #1346958

#제출 시각아이디문제언어결과실행 시간메모리
1346958ChocoTrampoline (info1cup20_trampoline)C++20
0 / 100
968 ms170504 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;
    vector<pair<ll,ll>>v(n+10);
    set<ll>st;
    fori(i,1,n){
        cin>>v[i].ff>>v[i].ss;
        st.ins(v[i].ff);
        st.ins(v[i].ss);
    }
    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;
        st.ins(qu[i].ff.ff); st.ins(qu[i].ff.ss);
        st.ins(qu[i].ss.ff); st.ins(qu[i].ss.ss);
    }
    ll cnt=0;
    map<ll,ll>comp;
    for(auto x: st){
        comp[x]=++cnt;
    }
    vector<vector<ll>>gr(cnt+10);
    map<pair<ll,ll>,ll>ind;
    fori(i,1,n){
        gr[comp[v[i].ff]].pb(comp[v[i].ss]);
        ind[{comp[v[i].ff],comp[v[i].ss]}]=i;
    }
    vector<vector<ll>>lca(n+10,vector<ll>(30,-1));
    // create binary lifting
    fori(i,2,cnt){
        if(!gr[i].size() || !gr[i-1].size())
        continue;
        for(auto x: gr[i]){
            auto it=upper_bound(all(gr[i-1]),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){
        pair<pair<ll,ll>,pair<ll,ll>>x=qu[i];
        ll fx=x.ff.ff,fy=x.ff.ss;
        ll ex=x.ss.ff,ey=x.ss.ss;
        if(fx==ex){
            if(fy<=ey){
                ans[i]=1;
                //cout<<"YES "<<i<<" "<<endl;
            }
            continue;
        }
        if(gr[fx].size()==0 || gr[ex-1].size()==0)
          continue;
        auto it=lower_bound(all(gr[fx]),fy);
        if(it==gr[fx].end())
          continue;
        ll ind1=ind[{fx,*it}];
        it=upper_bound(all(gr[ex-1]),ey);
        if(it==gr[ex-1].begin())
          continue;
        it--;
        ll ind2=ind[{ex-1,*it}];
        //cout<<ind1<<" "<<ind2<<endl;
        ll diff=ex-1-fx;
        for(ll i=30;i>=0;i--){
          if((1<<i)&diff)
          ind2=lca[ind2][i];
          if(ind2==-1)
            break;
        }
        if(ind2==ind1)
        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...