Submission #824543

#TimeUsernameProblemLanguageResultExecution timeMemory
824543AmylopectinRailway Trip 2 (JOI22_ho_t4)C++14
100 / 100
876 ms48884 KiB
#include <stdio.h> #include <iostream> #include <algorithm> using namespace std; const int mxn = 1e6 + 10; int n,le[40][mxn] = {},ri[40][mxn] = {},rel,rer,ldo[mxn] = {},rdo[mxn] = {}; int bui(int cl,int cr,int no,int v) { if(cl == cr) { // le[][no] = cl; // ri[][no] = cl; le[v][no] = -1; ri[v][no] = -1; return 0; } int mid = (cl+cr) / 2; bui(cl,mid,no*2,v); bui(mid+1,cr,no*2+1,v); le[v][no] = -1; ri[v][no] = -1; // le[][no] = min(le[][no*2],le[][no*2+1]); // ri[][no] = max(ri[][no*2],ri[][no*2+1]); return 0; } int ad(int cl,int cr,int no,int tl,int tr,int ava,int v) { if(cl > tr || cr < tl) { return 0; } if(cl >= tl && cr <= tr) { if(le[v][no] == -1) { le[v][no] = ava; } else { le[v][no] = min(le[v][no],ava); } if(ri[v][no] == -1) { ri[v][no] = ava; } else { ri[v][no] = max(ri[v][no],ava); } return 0; } int mid = (cl+cr) / 2; ad(cl,mid,no*2,tl,tr,ava,v); ad(mid+1,cr,no*2+1,tl,tr,ava,v); // le[][no] = min(le[][no*2],le[][no*2+1]); // ri[][no] = max(ri[][no*2],ri[][no*2+1]); return 0; } int bui2(int cl,int cr,int no,int ldow,int rdow,int v) { if(le[v][no] != -1) { if(ldow != -1) { ldow = min(ldow,le[v][no]); } else { ldow = le[v][no]; } } if(ri[v][no] != -1) { if(rdow != -1) { rdow = max(rdow,ri[v][no]); } else { rdow = ri[v][no]; } } if(cl == cr) { le[v][no] = ldow; ri[v][no] = rdow; return 0; } int mid = (cl+cr) / 2; bui2(cl,mid,no*2,ldow,rdow,v); bui2(mid+1,cr,no*2+1,ldow,rdow,v); if(le[v][no*2] == -1) { le[v][no] = le[v][no*2 +1]; } else if(le[v][no*2+1] == -1) { le[v][no] = le[v][no*2]; } else { le[v][no] = min(le[v][no*2],le[v][no*2+1]); } if(ri[v][no*2] == -1) { ri[v][no] = ri[v][no*2 +1]; } else if(ri[v][no*2+1] == -1) { ri[v][no] = ri[v][no*2]; } else { ri[v][no] = max(ri[v][no*2],ri[v][no*2+1]); } return 0; } int fii(int cl,int cr,int no,int tl,int tr,int v) { if(cl > tr || cr < tl) { return 0; } if(cl >= tl && cr <= tr) { if(le[v][no] != -1) rel = min(le[v][no],rel); if(ri[v][no] != -1) rer = max(ri[v][no],rer); return 0; } int mid = (cl+cr) / 2; fii(cl,mid,no*2,tl,tr,v); fii(mid+1,cr,no*2+1,tl,tr,v); return 0; } int bui3(int cl,int cr,int no,int v) { if(cl == cr) { if(le[v][no] != -1) { le[v][no] = min(le[v][no],cl); } if(ri[v][no] != -1) { ri[v][no] = max(ri[v][no],cl); } rel = le[v][no]; rer = ri[v][no]; fii(1,n,1,le[v][no],ri[v][no],v); le[v+1][no] = rel; ri[v+1][no] = rer; return 0; } int mid = (cl+cr) / 2; bui3(cl,mid,no*2,v); bui3(mid+1,cr,no*2+1,v); if(le[v+1][no*2] == -1) { le[v+1][no] = le[v+1][no*2 +1]; } else if(le[v+1][no*2+1] == -1) { le[v+1][no] = le[v+1][no*2]; } else { le[v+1][no] = min(le[v+1][no*2],le[v+1][no*2+1]); } if(ri[v+1][no*2] == -1) { ri[v+1][no] = ri[v+1][no*2 +1]; } else if(ri[v+1][no*2+1] == -1) { ri[v+1][no] = ri[v+1][no*2]; } else { ri[v+1][no] = max(ri[v+1][no*2],ri[v+1][no*2+1]); } return 0; } int main() { int i,j,k,m,q,cn,cm,fn,fm,ex,cou,cl,cr,clp,crp,of,fl,fr; scanf("%d %d %d",&n,&ex,&m); for(i=0; i<21; i++) { bui(1,n,1,i); } for(i=0; i<m; i++) { scanf("%d %d",&cn,&cm); if(cn < cm) { ad(1,n,1,cn,min(cn+ex-1,cm),cm,0); } else { ad(1,n,1,max(cn-ex+1,cm),cn,cm,0); } } bui2(1,n,1,-1,-1,0); for(i=0; i<21; i++) { bui3(1,n,1,i); } scanf("%d",&q); for(i=0; i<q; i++) { scanf("%d %d",&cn,&cm); cl = cn; cr = cn; of = 0; cou = 0; for(j=20; j>=0; j--) { rel = cl; rer = cr; fii(1,n,1,cl,cr,j); if(!(rel <= cm && cm <= rer)) { cou += (1<<j); cl = rel; cr = rer; } } cou ++; if(cou > m) { printf("-1\n"); } else { printf("%d\n",cou); } } }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:191:13: warning: unused variable 'k' [-Wunused-variable]
  191 |     int i,j,k,m,q,cn,cm,fn,fm,ex,cou,cl,cr,clp,crp,of,fl,fr;
      |             ^
Main.cpp:191:25: warning: unused variable 'fn' [-Wunused-variable]
  191 |     int i,j,k,m,q,cn,cm,fn,fm,ex,cou,cl,cr,clp,crp,of,fl,fr;
      |                         ^~
Main.cpp:191:28: warning: unused variable 'fm' [-Wunused-variable]
  191 |     int i,j,k,m,q,cn,cm,fn,fm,ex,cou,cl,cr,clp,crp,of,fl,fr;
      |                            ^~
Main.cpp:191:44: warning: unused variable 'clp' [-Wunused-variable]
  191 |     int i,j,k,m,q,cn,cm,fn,fm,ex,cou,cl,cr,clp,crp,of,fl,fr;
      |                                            ^~~
Main.cpp:191:48: warning: unused variable 'crp' [-Wunused-variable]
  191 |     int i,j,k,m,q,cn,cm,fn,fm,ex,cou,cl,cr,clp,crp,of,fl,fr;
      |                                                ^~~
Main.cpp:191:52: warning: variable 'of' set but not used [-Wunused-but-set-variable]
  191 |     int i,j,k,m,q,cn,cm,fn,fm,ex,cou,cl,cr,clp,crp,of,fl,fr;
      |                                                    ^~
Main.cpp:191:55: warning: unused variable 'fl' [-Wunused-variable]
  191 |     int i,j,k,m,q,cn,cm,fn,fm,ex,cou,cl,cr,clp,crp,of,fl,fr;
      |                                                       ^~
Main.cpp:191:58: warning: unused variable 'fr' [-Wunused-variable]
  191 |     int i,j,k,m,q,cn,cm,fn,fm,ex,cou,cl,cr,clp,crp,of,fl,fr;
      |                                                          ^~
Main.cpp:192:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  192 |     scanf("%d %d %d",&n,&ex,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:199:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  199 |         scanf("%d %d",&cn,&cm);
      |         ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:214:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  214 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
Main.cpp:217:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  217 |         scanf("%d %d",&cn,&cm);
      |         ~~~~~^~~~~~~~~~~~~~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...