Submission #1318382

#TimeUsernameProblemLanguageResultExecution timeMemory
1318382Muhammad_AneeqTrampoline (info1cup20_trampoline)C++20
100 / 100
480 ms39364 KiB
#include <bits/stdc++.h> using namespace std; int const N=2e5+10,LG=19; int ind[N][LG]={}; inline void solve() { int n,m,k; cin>>n>>m>>k; map<int,vector<pair<int,int>>>vals; vector<pair<int,int>>ed; for (int i=0;i<k;i++) { int x,y; cin>>x>>y; ed.push_back({x,y}); } sort(begin(ed),end(ed)); for (int i=0;i<k;i++) { int x=ed[i].first,y=ed[i].second; vals[x].push_back({y,i}); } for (auto& [i,j]:vals) sort(begin(j),end(j)); for (int i=0;i<k;i++) { int f=ed[i].first+1; int inds=i; if (vals.find(f)!=vals.end()) { pair<int,int>g={ed[i].second,0}; int z=lower_bound(begin(vals[f]),end(vals[f]),g)-begin(vals[f]); if (z!=vals[f].size()) inds=vals[f][z].second; } ind[i][0]=inds; } for (int i=1;i<LG;i++) for (int j=0;j+(1<<i)-1<k;j++) ind[j][i]=ind[ind[j][i-1]][i-1]; int q; cin>>q; while (q--) { int x1,x2,y1,y2; cin>>x1>>y1>>x2>>y2; if (x1==x2&&y1<=y2) { cout<<"Yes\n";continue; } if (x2<x1||y2<y1) { cout<<"No\n";continue; } int df=x2-x1-1; int ans=-1; if (vals.find(x1)!=vals.end()) { pair<int,int>g={y1,0}; int z=lower_bound(begin(vals[x1]),end(vals[x1]),g)-begin(vals[x1]); if (z!=vals[x1].size()) { int st=vals[x1][z].second; for (int i=0;i<LG;i++) { if ((1<<i)&df) st=ind[st][i]; } ans=st; } } if (ans!=-1&&(ed[ans].first==x2-1&&ed[ans].second<=y2)) { cout<<"Yes\n";continue; } cout<<"No\n"; } } int main() { ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); int t=1; for (int i=1;i<=t;i++) { 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...