Submission #17071

#TimeUsernameProblemLanguageResultExecution timeMemory
17071muratDancing Elephants (IOI11_elephants)C++98
100 / 100
5604 ms108528 KiB
#include "elephants.h" #include <bits/stdc++.h> using namespace std; #define foreach(it, x) for(type(x) it = x.begin(); it != x.end(); it++) #define type(x) __typeof(x.begin()) #define mp make_pair #define pb push_back #define nd second #define st first #define next sadas const int inf = 1e9 + 5; const int N = 2e6 + 5; int SQ; typedef pair< int , int > pii; typedef long long ll; int SQQ, sss, n, m, x, y, z, t, S, xx[N], wh[N]; pii next[N]; vector< pii > v[N]; set< pii > SS; pii take(int ind, int w) { int t = 0, ss = v[w][ind].st; while(w <= S && (!v[w].size() || (v[w].rbegin()->st) <= ss + m)) w++; if(w > S) return mp(inf + 5, inf + 5); return mp(lower_bound(v[w].begin(), v[w].end(), mp(ss + m + 1, 0)) - v[w].begin(), w); } int take() { pii cur = mp(0, 1); int ans = 0; while(!v[cur.nd].size()) cur.nd++; while(cur.nd < inf) { int u = v[cur.nd][cur.st].nd; if(next[u].st) { ans += next[u].st; cur.st = next[u].nd; } else { cur = take(cur.st, cur.nd); ans++; } } return ans; } void init(vector< pii > &v) { int ind = (int)v.size()-1; for(int i = (int) v.size() - 1; i >= 0; i--) { int zz = v[i].nd; while(ind >= 0 && v[ind] >= mp(v[i].st + m + 1, 0)) ind--; ind++; if(ind == v.size()) next[zz] = mp(0, i); else { int indd = v[ind].nd; next[zz] = mp(next[indd].st + 1, next[indd].nd); } ind--; } } void init() { vector< pii > ss; for(int i = 1; i <= S; i++) { foreach(it, v[i]) ss.pb(*it); v[i].clear(); } if(!sss) { for(int i = 1; i <= n; i++) ss.pb(mp(xx[i], i)); } int s = 0; S = 0; vector< pii > :: iterator it2 = ss.end(); it2--; vector< pii > temp; foreach(it, ss) { temp.pb(*it); if(++s % SQ == 0 || (it == it2)) { v[++S] = temp; foreach(it, temp) wh[it->nd] = S; init(v[S]); temp.clear(); } } ss.clear(); } void del(int x, int y) { int ww = wh[y]; v[ww].erase(find(v[ww].begin(), v[ww].end(), mp(x, y))); init(v[ww]); } void ins(vector< pii > &v, pii x) { vector< pii > temp; int t = 0; foreach(it, v) { if(!t && *it > x) { temp.pb(x); t = 1; } temp.pb(*it); }if(!t) temp.pb(x); v = temp; temp.clear(); } void add(int x, int y) { int ww = S; while(ww > 1 && (!v[ww].size() || *v[ww].begin() > mp(x, y))) ww--; wh[y] = ww; ins(v[ww], mp(x, y)); init(v[ww]); } void init(int N, int L, int X[]) { n = N; m = L; SQ = 500; SQQ = 700; for(int i = 0; i < n; i++) { xx[i+1] = X[i]; SS.insert(mp(X[i], i+1)); } init(); } int update(int i, int y) { i++; del(xx[i], i); add(xx[i] = y, i); if(++sss % SQQ == 0) init(); return take(); }
#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...