Submission #1200041

#TimeUsernameProblemLanguageResultExecution timeMemory
1200041WH8Trampoline (info1cup20_trampoline)C++20
0 / 100
2093 ms100504 KiB
#include <bits/stdc++.h> using namespace std; #define int long long map<pair<int,int>, vector<pair<int,int>>> twok; //~ pair<int,int> par(pair<int,int> c){ //~ if(p[c].first==0){ //~ return c; //~ } //~ return p[c]=par(p[c]); //~ } pair<int,int> kpar(pair<int,int> c, int k){ for(int i=0;i<20;i++){ if(1<<i & k){ c=twok[c][i]; } } return c; } signed main(){ int r,c,n; cin>>r>>c>>n; map<int,vector<int>> rs; vector<pair<int,int>> g; for(int i=0;i<n;i++){ int a,b;cin>>a>>b; rs[a].push_back(b); g.push_back({a,b}); } for(auto & it : rs){ sort(it.second.begin(),it.second.end()); } for(auto & it : rs){ int x=it.first; for(auto y:it.second){ //~ printf("at %lld %lld \n",x,y); fflush(stdout); auto nxt=lower_bound(rs[x+1].begin(),rs[x+1].end(),y); if(nxt != rs[x+1].end()){ //~ printf("points to %lld %lld\n",x+1, (*nxt)); //~ fflush(stdout); twok[{x,y}].push_back({x+1, (*nxt)}); } } } for(auto [x,y]:g){ if((int)twok[{x,y}].size() < 20)twok[{x,y}].resize(20); } for(int i=1;i<20;i++){ for(auto [x,y]:g){ //~ printf("calculating 2^%lld par of %lld %lld\n",i,x,y); pair<int,int> fpar=twok[{x,y}][i-1]; //~ printf("calculating 2^%lld par of %lld %lld, fpar is %lld %lld\n",i,x,y,fpar.first,fpar.second); //~ fflush(stdout); if(fpar.first==0) continue; else twok[{x,y}][i]=twok[fpar][i-1]; //~ printf("done with %lld %lld\n", x,y); //~ fflush(stdout); } } int t;cin>>t; for(int i=0;i<t;i++){ int sx, sy, nx, ny;cin>>sx>>sy>>nx>>ny; if(sx == nx){ cout<<"Yes\n"; continue; } pair<int,int> st={sx, 1e15}; auto it=lower_bound(rs[sx].begin(),rs[sx].end(),sy); if(it==rs[sx].end()){ cout<<"No\n"; continue; } st.second=(*it); st=kpar(st, nx-sx-1); if(st.first==0){ cout<<"No\n"; } else { if(st.second <= ny){ cout<<"Yes\n"; } else cout<<"No\n"; } } }
#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...