Submission #118187

#TimeUsernameProblemLanguageResultExecution timeMemory
118187imyujinBitaro, who Leaps through Time (JOI19_timeleap)C++14
0 / 100
313 ms31324 KiB
#include<stdio.h> #include<algorithm> using namespace std; #define MAXN 300005 typedef pair<long long, int> pi; const int INF=1e9; int N, rn; int L[MAXN], R[MAXN]; int T[MAXN], A[MAXN], B[MAXN], C[MAXN], D[MAXN]; int LL[2*MAXN], RR[2*MAXN]; int lmax[6*MAXN], rmin[6*MAXN]; int root[800]; pi dp[4*MAXN]; void updseg(int x, int idx, int l, int r){ if(l==r){ lmax[idx]=l; rmin[idx]=l; } else{ int m=(l+r)/2; if(x<=m) updseg(x, idx*2, l, m); else updseg(x, idx*2+1, m+1, r); lmax[idx]=LL[lmax[idx*2]]>=LL[lmax[idx*2+1]]?lmax[idx*2]:lmax[idx*2+1]; rmin[idx]=RR[rmin[idx*2]]<=RR[rmin[idx*2+1]]?rmin[idx*2]:rmin[idx*2+1]; } } int gbigl(int x, int y, int idx, int l, int r){ //printf("*x=%d, y=%d, l=%d, r=%d\n", x, y, l, r); if(LL[lmax[idx]]<y) return r+1; if(l==r) return l; int m=(l+r)/2; if(x>m) return gbigl(x, y, idx*2+1, m+1, r); int t=gbigl(x, y, idx*2, l, m); return t==m+1?gbigl(x, y, idx*2+1, m+1, r):t; } int gsmar(int x, int y, int idx, int l, int r){ if(RR[rmin[idx]]>y) return r+1; if(l==r) return l; int m=(l+r)/2; if(x>m) return gsmar(x, y, idx*2+1, m+1, r); int t=gsmar(x, y, idx*2, l, m); return t==m+1?gsmar(x, y, idx*2+1, m+1, r):t; } pi move(int x1, int x2, int y1){ int x=x1, y=y1<2*N?LL[y1]:RR[y1-2*N]; pi ans=make_pair(0, y1); while(x<x2){ x++; if(LL[x]>y){ ans.second=x; y=LL[x]; } else if(RR[x]<y){ ans.first+=y-RR[x]; ans.second=x+2*N; y=RR[x]; } } return ans; } int gr(int x){ int r=0; while(r<rn&&root[r+1]<=x) r++; return r; } void update(int x, int l, int r){ //printf("[%d %d %d]\n", x, l, r); LL[x]=l; RR[x]=r; updseg(x, 1, 0, 2*N-3); r=gr(x); if(r>0) for(int i=root[r-1]; i<root[r]; i++) for(int j=i; j<=i+2*N; j+=2*N) dp[j]=move(root[r], root[r+1], j); } void print(){ for(int i=0; i<2*N-2; i++) printf("%d ", LL[i]); printf("\n"); for(int i=0; i<2*N-2; i++) printf("%d ", RR[i]); printf("\n[%d %d]\n", lmax[1], rmin[1]); for(int i=0; i<rn-1; i++) for(int j=root[i]; j<root[i+1]; j++) for(int k=j; k<=j+2*N; k+=2*N) dp[k]=move(root[i+1], root[i+2], k); for(int i=0; i<2; i++) for(int j=0; j<2*N-2; j++) printf("dp[%d]=(%d %d)\n", i*2*N+j, dp[i*2*N+j].first, dp[i*2*N+j].second); printf("\n"); } int main(){ int Q; //freopen("input.txt", "r", stdin); scanf("%d%d", &N, &Q); for(int i=0; i<N-1; i++) scanf("%d%d", L+i, R+i); for(int i=0; i<Q; i++){ scanf("%d%d%d%d", T+i, A+i, B+i, C+i); if(T[i]==2) scanf("%d", D+i); } for(int i=0; i<N-1; i++){ LL[i]=L[i]-i; RR[i]=R[i]-i-1; updseg(i, 1, 0, 2*N-3); LL[2*N-3-i]=L[i]+i; RR[2*N-3-i]=R[i]+i-1; updseg(2*N-3-i, 1, 0, 2*N-3); } for(rn=1; (rn+1)*(rn+1)<=2*N-3; rn++); root[0]=0; for(int i=1; i<=rn; i++) root[i]=root[i-1]+(2*N-3)/rn+(i<=(2*N-3)%rn?1:0); //for(int i=0; i<=rn; i++) printf("%d ", root[i]); //printf("\n"); //print(); for(int i=0; i<Q; i++){ if(T[i]==1){ update(A[i]-1, B[i]-A[i]+1, C[i]-A[i]); update(2*N-2-A[i], B[i]+A[i]-1, C[i]+A[i]-2); //print(); } else{ int x1, y1, x2, y2; if(A[i]<C[i]){ x1=A[i]-1; y1=B[i]-A[i]+1; x2=C[i]-2; y2=D[i]-C[i]+1; } else{ x1=2*N-1-A[i]; y1=B[i]+A[i]-2; x2=2*N-2-C[i]; y2=D[i]+C[i]-2; } //printf("x1=%d, y1=%d, x2=%d, y2=%d\n", x1, y1, x2, y2); int lb=gbigl(x1, y1+1, 1, 0, 2*N-3), rs=gsmar(x1, y1-1, 1, 0, 2*N-3); //printf("lb=%d, rs=%d\n", lb, rs); int k=lb<rs?lb:rs+2*N, x3=min(lb, rs); long long ans=lb<rs?0:y1-RR[rs]; if(x3>x2){ printf("%d\n", y1<y2?0:y1-y2); continue; } int r1=gr(x3), r2=gr(x2); if(r1==r2){ pi p=move(x3, x2, k); int y=p.second<2*N?LL[p.second]:RR[p.second-2*N]; //printf("x3=%d, x2=%d, k=%d, p=(%d, %d), y=%d\n", x3, x2, k, p.first, p.second, y); printf("%lld\n", ans+(y>y2?y-y2:0)); continue; } pi p=move(x3, root[r1+1], k); //printf("r1=%d, r2=%d, p=(%d, %d)\n", r1, r2, p.first, p.second); ans+=p.first; for(int j=r1+1; j<r2-1; j++){ p=move(root[j], root[j+1], p.second); ans+=p.first; } p=move(root[r2], x2, p.second); //printf("p=(%d, %d)\n", p.first, p.second); ans+=p.first; int y=p.second<2*N?LL[p.second]:RR[p.second-2*N]; printf("%lld\n", ans+(y>y2?y-y2:0)); } } return 0; }

Compilation message (stderr)

timeleap.cpp: In function 'void print()':
timeleap.cpp:93:125: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
  for(int i=0; i<2; i++) for(int j=0; j<2*N-2; j++) printf("dp[%d]=(%d %d)\n", i*2*N+j, dp[i*2*N+j].first, dp[i*2*N+j].second);
                                                                                        ~~~~~~~~~~~~~~~~~                    ^
timeleap.cpp: In function 'int main()':
timeleap.cpp:101:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &Q);
  ~~~~~^~~~~~~~~~~~~~~~
timeleap.cpp:102:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<N-1; i++) scanf("%d%d", L+i, R+i);
                           ~~~~~^~~~~~~~~~~~~~~~~~
timeleap.cpp:104:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", T+i, A+i, B+i, C+i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:105:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   if(T[i]==2) scanf("%d", D+i);
               ~~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...