제출 #406232

#제출 시각아이디문제언어결과실행 시간메모리
406232pure_mem코끼리 (Dancing Elephants) (IOI11_elephants)C++14
97 / 100
9045 ms12644 KiB
#include "elephants.h" #include <bits/stdc++.h> #define X first #define Y second #define MP make_pair #define ll long long using namespace std; const int MAXN = 150000, BS = 300, INF = 1e9 + 7; int n, w, p[MAXN], ps[MAXN], buck[MAXN]; vector< pair< int, int > > bl[MAXN / BS + 3]; int dp1[MAXN], dp2[MAXN]; void trick(vector< pair<int, int> > &cur, pair<int, int> val){ vector< pair<int, int> > tmp; for(pair<int, int> v: cur){ if(val == v) continue; tmp.push_back(v); } cur.swap(tmp), tmp.clear(); } void upd(int id, bool keep = 0){ if(!keep) sort(bl[id].begin(), bl[id].end()); for(int i = (int)bl[id].size() - 1, j = (int)bl[id].size();i >= 0;i--){ int me = bl[id][i].Y, pos = bl[id][i].X; buck[me] = id; while(j - 1 >= i && bl[id][j - 1].X > pos + w) j--; if(j == (int)bl[id].size()) dp1[me] = 1, dp2[me] = pos + w; else dp1[me] = dp1[bl[id][j].Y] + 1, dp2[me] = dp2[bl[id][j].Y]; } } void build(){ sort(ps, ps + n, [](int x, int y){return p[x] < p[y];}); for(int i = 0, j = 0;i < n;i += BS, j++) bl[j].clear(); for(int i = 0, j = 0, z = 1;i < n;i++, (z == BS ? z = 1, j++: z++)) bl[j].push_back(MP(p[ps[i]], ps[i])); for(int i = 0, j = 0;i < n;i += BS, j++) upd(j, 1); } void init(int N, int L, int X[]){ n = N, w = L; for(int i = 0;i < n;i++) p[i] = X[i], ps[i] = i; build(); } int solve(){ int cnt = 0, pos = 0; for(int j = 0;;j++){ if(bl[j].empty()) break; else if(bl[j].back().X < pos) continue; pair<int, int> tmp = *upper_bound(bl[j].begin(), bl[j].end(), MP(pos, -1)); cnt += dp1[tmp.Y], pos = dp2[tmp.Y] + 1; } return cnt; } int cntQ; int update(int i, int y){ cntQ++; if(cntQ == BS){ p[i] = y, cntQ = 0; build(); } else{ trick(bl[buck[i]], MP(p[i], i)), upd(buck[i]); p[i] = y; for(int j = 0;;j++){ int left = (j ? bl[j - 1].back().X: 0), right = (bl[j + 1].empty() ? INF: bl[j + 1][0].X); if(left <= y && y <= right){ bl[j].push_back(MP(y, i)), upd(j); break; } } } return solve(); }
#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...