Submission #679623

#TimeUsernameProblemLanguageResultExecution timeMemory
679623heeheeheehaawTrampoline (info1cup20_trampoline)C++17
100 / 100
995 ms28436 KiB
#include <iostream> #include <algorithm> #define cell(x,y) kus(x,y) using namespace std; struct cell { int x,y; bool operator <(const cell a) const { return x<a.x || (a.x==x && y<a.y); } } green[200001]; int n; static cell kus(int x, int y) { cell rez; rez.x=x; rez.y=y; return rez; } static int findfirst(int x, int y) { cell val=cell(x,y); int temp,bound=-1; for(int i=(1<<17); i>0; i>>=1) { temp=min(n,bound+i); if(green[temp]<val) bound=temp; } return bound+1; } int st[200001][18]; int main() { int q,r,c; cin >> r >> c >> n; for(int i=0,a,b; i<n; i++) { cin >> a >> b; green[i]=cell(a,b); } green[n]=cell(r+1,c+1); sort(green,green+n); for(int i=0;i<n; i++) { st[i][0]=findfirst(green[i].x+1,green[i].y); if(green[st[i][0]].x!=green[i].x+1) st[i][0]=n; } st[n][0]=n; for(int step=1; step<18; step++) { for(int j=0; j<=n;j++) { st[j][step]=st[st[j][step-1]][step-1]; } } cin >> q; for(int tc=0,x1,x2,y1,y2,diff,curr; tc<q; tc++) { cin >> x1 >> y1 >> x2 >> y2; if(x2-x1>n || x2<x1 || y2<y1) cout << "No\n"; else if(x1==x2) { cout << "Yes\n"; } else { diff=x2-x1-1; curr=findfirst(x1,y1); if(green[curr].x!=x1) cout << "No\n"; else { for(int i=0; i<18; i++) { if((1<<i)&diff) curr=st[curr][i]; } cout << (green[curr].x+1==x2 && green[curr].y<=y2?"Yes\n":"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...