Submission #25494

#TimeUsernameProblemLanguageResultExecution timeMemory
25494BruteforcemanDancing Elephants (IOI11_elephants)C++11
100 / 100
6546 ms25108 KiB
#include "elephants.h" #include "bits/stdc++.h" using namespace std; int n; int a[150010]; int len; const int magic = 390; vector <int> v[1000]; vector <int> dp[1000]; vector <int> nxt[1000]; int bucket[150010]; int tot; int counter; bool cmp(int x, int y) { return a[x] < a[y]; } int search(int b, int e, int block, int value) { if(b == e) { return a[v[block][b]] <= value ? b : -1; } int m = (b + e + 1) >> 1; if(a[v[block][m]] <= value) return search(m, e, block, value); else return search(b, m-1, block, value); } void get_done(int b) { if(v[b].empty()) return ; int sz = v[b].size(); nxt[b].resize(sz); dp[b].resize(sz); int pointer = sz-1; for(int i = sz-1; i >= 0; i--) { while(pointer >= 0 && a[v[b][i]] + len < a[v[b][pointer]]) { --pointer; } int id = pointer; if(id == sz - 1) { dp[b][i] = 1; nxt[b][i] = a[v[b][i]] + len; } else { dp[b][i] = dp[b][id + 1] + 1; nxt[b][i] = nxt[b][id + 1]; } } } void init(int N, int L, int X[]) { tot = (N-1) / magic; len = L; n = N; for(int i = 0; i < n; i++) { a[i] = X[i]; } for(int i = 0; i < n; i++) { v[i / magic].push_back(i); bucket[i] = i / magic; } for(int i = 0; i <= tot; i++) { get_done(i); } counter = 0; } int query() { int ans = 0; int cover = -1; for(int i = 0; i <= tot; i++) { if(v[i].empty()) continue; int sz = v[i].size(); int u = search(0, sz-1, i, cover); if(u < sz-1) { ans += dp[i][u + 1]; cover = nxt[i][u + 1]; } } return ans; } void rebuild() { vector <int> pos; for(int i = 0; i <= tot; i++) { for(auto j : v[i]) { pos.push_back(j); } v[i].clear(); } for(int i = 0; i < n; i++) { bucket[pos[i]] = i / magic; v[i / magic].push_back(pos[i]); } for(int i = 0; i <= tot; i++) { get_done(i); } } int update(int i, int y) { ++counter; if(counter == magic) { counter = 0; rebuild(); } int b1 = bucket[i]; int b2 = tot; v[b1].erase(find(v[b1].begin(), v[b1].end(), i)); a[i] = y; for(int x = 0; x <= tot; x++) { if(v[x].empty()) continue; if(a[i] <= a[v[x].back()]) { b2 = x; break; } } bucket[i] = b2; v[b2].push_back(i); int pointer = v[b2].size() - 1; while(pointer > 0 && a[v[b2][pointer - 1]] > a[v[b2][pointer]]) { swap(v[b2][pointer - 1], v[b2][pointer]); --pointer; } get_done(b1); get_done(b2); return query(); }
#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...