Submission #17076

#TimeUsernameProblemLanguageResultExecution timeMemory
17076erdemkirazDancing Elephants (IOI11_elephants)C++98
100 / 100
8040 ms23860 KiB
#include "elephants.h" #include <bits/stdc++.h> using namespace std; #define type(x) __typeof((x).begin()) #define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++) typedef long long ll; typedef pair < int, int > ii; const int inf = 1e9 + 333; const ll linf = 1e18 + inf; const int N = 150000 + 5; const int K = 1500; const int T = N / K + 5; int n, l; int a[N], gr[N], nxt[N], need[N]; vector < ii > v[T]; void rebuild(int i) { int last = 0; if(v[i].size()) last = v[i].back().first; int pos = (int) v[i].size() - 1; for(int j = (int) v[i].size() - 1; j >= 0; j--) { int x = v[i][j].first; int id = v[i][j].second; gr[id] = i; if(x + l >= last) { nxt[id] = id; need[id] = 0; } else { while(pos > j + 1 and x + l < v[i][pos - 1].first) pos--; nxt[id] = nxt[v[i][pos].second]; need[id] = need[v[i][pos].second] + 1; } } } ii b[N]; void init(bool flag = 0) { if(flag) { for(int i = 0; i < n; i++) b[i] = ii(a[i], i); } else { int sz = 0; for(int i = 0; i * K < n; i++) { for(int j = 0; j < v[i].size(); j++) b[sz++] = v[i][j]; } } int ind = 0; for(int i = 0; i * K < n; i++) { v[i].clear(); for(int j = i * K; j < n and j < (i + 1) * K; j++) { v[i].push_back(b[j]); } ind = i; } for(int i = ind; i >= 0; i--) rebuild(i); } void init(int N, int L, int X[]) { n = N; l = L; for(int i = 0; i < n; i++) { a[i] = X[i]; } a[n] = 2 * inf; init(1); } int upCnt = 0; int update(int i, int x) { int ind = gr[i]; v[ind].erase(lower_bound(v[ind].begin(), v[ind].end(), ii(a[i], i))); rebuild(ind); a[i] = x; for(int j = 0; j * K < n; j++) { ind = j; if(v[j].size() and ii(a[i], i) <= v[j].back()) break; } v[ind].insert(lower_bound(v[ind].begin(), v[ind].end(), ii(a[i], i)), ii(a[i], i)); rebuild(ind); upCnt++; if(upCnt == 1500) { upCnt = 0; init(); } int pos = v[0].front().second, ans = 0; while(pos < n) { if(nxt[pos] == pos) { ans++; int ind = gr[pos] + 1; while(ind * K < n and a[pos] + l >= v[ind].back().first) ind++; if(ind * K >= n) break; pos = lower_bound(v[ind].begin(), v[ind].end(), ii(a[pos] + l + 1, 0)) -> second; } else { ans += need[pos]; pos = nxt[pos]; } } 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...