Submission #16427

#TimeUsernameProblemLanguageResultExecution timeMemory
16427choyi0521Dancing Elephants (IOI11_elephants)C++14
100 / 100
4283 ms21316 KiB
#include "elephants.h" #include<algorithm> using namespace std; const int MAX_N = 150000, MAX_RTN =388; int n,l,x[MAX_N]; int rtn; struct st{ int sz; int x[MAX_RTN*2],d[MAX_RTN * 2],cnt[MAX_RTN*2]; }e[MAX_RTN]; void init(int N, int L, int X[]){ n = N; l = L; rtn = sqrt(N-1)+1; for (int i = 0; i < N; i++) e[i / rtn].x[e[i / rtn].sz++]=x[i] = X[i]; } void UpdateBucket(int b){ int tpos = e[b].sz; for (int i = e[b].sz - 1; i >= 0; i--){ while (e[b].x[tpos - 1] - e[b].x[i] > l) tpos--; if (tpos == e[b].sz){ e[b].d[i] = e[b].x[i]; e[b].cnt[i] = 1; } else{ e[b].d[i] = e[b].d[tpos]; e[b].cnt[i] = e[b].cnt[tpos] + 1; } } } void Restructure(){ int tx[MAX_N],tcnt=0; for (int i = 0; i < rtn; i++){ for (int j = 0; j < e[i].sz; j++) tx[tcnt++] = e[i].x[j]; e[i].sz = 0; } for (int i = 0; i < n; i++) e[i / rtn].x[e[i / rtn].sz++] = tx[i]; for (int i = 0; i < rtn; i++) UpdateBucket(i); } void Delete(int tx){ int b,i; for (b = 0; b < rtn; b++) if (e[b].sz && tx <= e[b].x[e[b].sz - 1]) break; if(b==rtn) b--; for (i = 0; e[b].x[i] != tx; i++); e[b].sz--; for (; i<e[b].sz; i++) e[b].x[i] = e[b].x[i + 1]; UpdateBucket(b); } void Add(int tx){ int b; for (b = 0; b < rtn; b++) if (e[b].sz && tx <= e[b].x[e[b].sz - 1]) break; if (b == rtn) b--; for (int i = 0; i < e[b].sz; i++) if (e[b].x[i]>tx) swap(e[b].x[i], tx); e[b].x[e[b].sz++] = tx; UpdateBucket(b); } int ucnt; int update(int i, int y){ if (ucnt++%rtn == 0) Restructure(); Delete(x[i]); Add(x[i] = y); int ans = 0, b=-1, tx=-1, t; while (++b < rtn){ t = upper_bound(e[b].x, e[b].x + e[b].sz, tx) - e[b].x; if (t == e[b].sz) continue; ans += e[b].cnt[t]; tx = e[b].d[t] + l; } return ans; }
#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...