Submission #263184

#TimeUsernameProblemLanguageResultExecution timeMemory
263184dantoh000Dancing Elephants (IOI11_elephants)C++14
100 / 100
4951 ms16340 KiB
#include <bits/stdc++.h> #define K 500 using namespace std; //#include "elephants.h" int n, l, x[150005]; int tmp[150005]; struct BUCKET{ int a[150005], ct[150005], r[150005], sz; void comp(){ int k = sz-1; for (int i = sz-1; i >= 0; i--){ while (k > i && a[k-1] - a[i] > l) k--; if (a[sz-1] - a[i] <= l){ ct[i] = 1; r[i] = a[i]+l; } else ct[i] = ct[k]+1, r[i] = r[k]; //printf("%d -> %d: ct = %d, r = %d\n",a[i],a[k],ct[i],r[i]); } } } bk[305]; void init(int N, int L, int X[]) { n = N; l = L; for (int i = 0; i < n; i++) x[i] = X[i]; for (int i = 0; i <= n/K; i++){ bk[i].sz = 0; for (int j = i*K; j < min((i+1)*K,n); j++){ bk[i].a[j%K] = x[j]; bk[i].sz++; } bk[i].comp(); } } void rebuild_all(){ //printf("REBUILD ALL"); int N = 0; for (int i = 0; i <= n/K; i++){ for (int j = 0; j < bk[i].sz; j++){ tmp[N++] = bk[i].a[j]; } } for (int i = 0; i <= n/K; i++){ bk[i].sz = 0; for (int j = i*K; j < min((i+1)*K,n); j++){ bk[i].a[j%K] = tmp[j]; bk[i].sz++; } bk[i].comp(); } } void add(int x){ //printf("adding %d\n",x); for (int i = 0; i <= n/K; i++){ if (i == (n-1)/K || (bk[i].sz && ((bk[i].a[0] > x) || (bk[i].a[0] <= x && x < bk[i+1].a[0])) )){ //printf("adding to bucket %d\n",i); if (bk[i].sz == 0 || bk[i].a[0] > x){ //printf("position %d\n",0); for (int k = bk[i].sz-1; k >= 0; k--){ bk[i].a[k+1] = bk[i].a[k]; } bk[i].a[0] = x; } else{ for (int j = 0; j < bk[i].sz; j++){ if ((bk[i].a[j] <= x && x < bk[i].a[j+1]) || j+1 == bk[i].sz){ //printf("position %d\n",j+1); for (int k = bk[i].sz-1; k >= j+1; k--){ bk[i].a[k+1] = bk[i].a[k]; } bk[i].a[j+1] = x; break; } } } bk[i].sz++; bk[i].comp(); break; } } } void del(int x){ // printf("deleting %d\n",x); for (int i = 0; i <= n/K; i++){ if (bk[i].sz == 0) continue; if (bk[i].a[0] <= x && x <= bk[i].a[bk[i].sz-1]){ //printf("deleting from bucket %d\n",i); for (int j = 0; j < bk[i].sz; j++){ if (bk[i].a[j] == x){ //printf("position %d\n",j); for (int k = j; k < bk[i].sz; k++){ bk[i].a[k] = bk[i].a[k+1]; } break; } } bk[i].a[bk[i].sz] = 0; bk[i].sz--; bk[i].comp(); break; } } } int hmmmmm; int solve(){ //printf("solving\n"); int curpos = -1; int ans = 0; for (int i = 0; i <= n/K; i++){ if (bk[i].sz == 0 || curpos >= bk[i].a[bk[i].sz-1]) continue; //printf("%d ",curpos); int nx = upper_bound(bk[i].a, bk[i].a+bk[i].sz,curpos) - bk[i].a; //printf("-> nx = %d (%d), ",nx,bk[i].a[nx]); //printf("add %d to %d\n",bk[i].ct[nx],ans); ans += bk[i].ct[nx]; curpos = bk[i].r[nx]; } return ans; } void debug(){ int last = -1; int cur = 0; for (int i = 0; i <= n/K; i++){ //printf("bucket %d: ",i); for (int j = 0; j < bk[i].sz; j++){ //printf("%d ",bk[i].a[j]); assert(bk[i].a[j] >= last); last= bk[i].a[j]; } // printf("\n"); } } int numQ = 0; int update(int i, int y) { hmmmmm++; //printf("up %d\n",hmmmmm); //printf("update %d %d->%d\n",i,x[i],y); if (++numQ == K){ rebuild_all(); numQ = 0; } del(x[i]); x[i] = y; add(x[i]); //debug(); return solve(); }

Compilation message (stderr)

elephants.cpp: In function 'void debug()':
elephants.cpp:126:9: warning: unused variable 'cur' [-Wunused-variable]
  126 |     int cur = 0;
      |         ^~~
#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...