Submission #769145

#TimeUsernameProblemLanguageResultExecution timeMemory
769145Dan4LifeDancing Elephants (IOI11_elephants)C++17
26 / 100
9025 ms2380 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define sz(a) (int)a.size() #define all(a) a.begin(),a.end() const int mxN = (int)5e4+10; const int B = 240; int n, L, x[mxN]; using ar = array<int,3>; struct Block{ set<int> S; set<ar>S2; Block(){} void recalc(){ S2.clear(); auto itr = end(S); while(itr!=begin(S)){ itr--; auto it2 = S2.lower_bound({*itr+L+1,-1,-1}); if(it2==end(S2)) S2.insert({*itr,1,*itr+L+1}); else S2.insert({*itr,(*it2)[1]+1, (*it2)[2]}); } } Block(set<int> XD){ S.swap(XD); recalc(); } void add(int x){ if(S.count(x)) return; S.insert(x); recalc(); } void rem(int x){ if(!S.count(x)) return; S.erase(x); recalc(); } }; vector<Block> bl; void combine(int i, int j){ if(i>j) swap(i,j); auto S = bl[i].S, S2 = bl[j].S; if(sz(S)<sz(S2)) S.swap(S2); for(auto u : S2) S.insert(u); bl.erase(begin(bl)+j); bl.erase(begin(bl)+i); bl.insert(begin(bl)+i,Block(S)); } void divide(int i){ auto S2 = bl[i].S; set<int> S1; S1.clear(); int xd = sz(S2); xd/=2; while(xd--){ auto cur = *begin(S2); S1.insert(cur); S2.erase(cur); } bl.erase(begin(bl)+i); bl.insert(begin(bl)+i,Block(S2)); bl.insert(begin(bl)+i,Block(S1)); } void init(int N, int l, int X[]){ bl.pb({}); L = l; n = N; for(int i = 0; i < n; i++){ x[i] = X[i]; bl[sz(bl)-1].add(x[i]); if(sz(bl[sz(bl)-1].S)>B) divide(sz(bl)-1); } } int update(int p, int y){ for(int i = 0; i < sz(bl); i++){ if(bl[i].S.count(x[p])){ bl[i].rem(x[p]); while(i and sz(bl[i].S)+sz(bl[i-1].S) <= B) combine(i-1,i),i--; while(i<sz(bl)-1 and sz(bl[i].S)+sz(bl[i+1].S) <= B) combine(i,i+1),i++; break; } } x[p] = y; for(int i = 0; i < sz(bl); i++){ if(i==sz(bl)-1 or *(--end(bl[i].S)) >= x[p]){ bl[i].add(x[p]); if(sz(bl[i].S)>B) divide(i); break; } } int ans = 0, pos = 0; for(Block cur : bl){ auto S = cur.S; auto S2 = cur.S2; if(*(--end(S))<pos) continue; auto itr = *S2.lower_bound({pos,-1,-1}); ans+=itr[1], pos = itr[2]; } 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...