Submission #1215333

#TimeUsernameProblemLanguageResultExecution timeMemory
1215333JooDdaeDancing Elephants (IOI11_elephants)C++20
26 / 100
302 ms2884 KiB
#include "elephants.h" #include <bits/stdc++.h> using namespace std; using ll = long long; const int sq = 400; int X[150015], L; struct group { int x[808], p[808], r[808], sz; void update() { for(int i=sz-1, j=sz;i>=0;i--) { while(j > i && x[j-1]-x[i] > L) j--; if(j == sz) r[i] = x[i], p[i] = 1; else r[i] = r[j], p[i] = p[j]+1; } } void add(int u) { x[sz++] = u; for(int i=sz-1;i>0;i--) if(x[i] < x[i-1]) swap(x[i], x[i-1]); update(); } void erase(int u) { int k = 0; while(x[k] != u) k++; for(int i=k+1;i<sz;i++) swap(x[i-1], x[i]); sz--; update(); } } g[404]; int n, cnt, in[150015]; void rebuild() { } void init(int N, int L, int X[]) { ::L = L; for(int i=0;i<N;i++) ::X[i] = X[i], in[i] = i/sq, g[i/sq].add(X[i]); } int update(int i, int y) { g[in[i]].erase(X[i]); X[i] = y, in[i] = sq-1; while(in[i] && (!g[in[i]].sz || y < g[in[i]].x[0])) in[i]--; g[in[i]].add(y); if(++cnt == sq) rebuild(), cnt = 0; int ans = 0, R = -1; for(int i=0;i<sq;i++) if(g[i].sz && R < g[i].x[g[i].sz-1]) { int s = 0, e = g[i].sz; while(s <= e) { int mid = (s+e) >> 1; if(g[i].x[mid] <= R) s = mid+1; else e = mid-1; } ans += g[i].p[s], R = g[i].r[s]+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...