제출 #1089749

#제출 시각아이디문제언어결과실행 시간메모리
1089749ymm코끼리 (Dancing Elephants) (IOI11_elephants)C++17
97 / 100
1432 ms25748 KiB
#include "elephants.h" #include <bits/stdc++.h> #define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x) #define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x) typedef long long ll; typedef std::pair<int, int> pii; typedef std::pair<ll , ll > pll; using namespace std; int L; struct Part { vector<int> Ps; vector<pii> ans; void calc_ans() { ans.resize(Ps.size()); if (ans.empty()) return; ans.back() = {1, Ps.back() + L}; size_t ptr = ans.size(); LoopR (i,0,(ll)ans.size()-1) { while (Ps[ptr-1] - Ps[i] >= L) --ptr; ans[i].first = ptr == ans.size()? 1: ans[ptr].first + 1; ans[i].second = ptr == ans.size()? Ps[i] + L: ans[ptr].second; } } // vec must be sorted // O(vec.size()) Part(const vector<int> &vec) { Ps = vec; calc_ans(); } auto lower_bound(int x) { // implement caching mechanism if needed return std::lower_bound(Ps.begin(), Ps.end(), x); } // O(log(Ps.size())) pii get(int p) { auto it = lower_bound(p); if (it == Ps.end()) return {0, p}; return ans[it - Ps.begin()]; } // O(Ps.size()) void put(int x) { auto it = lower_bound(x); Ps.insert(it, x); calc_ans(); } // O(Ps.size()) void remove(int x) { auto it = lower_bound(x); assert(it != Ps.end() && *it == x); Ps.erase(it); calc_ans(); } }; struct PartList { vector<Part> parts; vector<int> bounds; map<int, int> pos_cnt; static constexpr int S = 1024; // O(nlog(n)) void init(vector<int> vec) { pos_cnt.clear(); sort(vec.begin(), vec.end()); for (int x : vec) pos_cnt[x]++; repart(vec); } // Ps must be sorted // O(Ps.size()) void repart(const vector<int> &Ps) { bounds.clear(); parts.clear(); for (size_t i = 0; i < Ps.size(); i += S) { size_t j = min<ll>(i + S, Ps.size()); if (j != Ps.size()) bounds.push_back(Ps[j]); parts.emplace_back(vector(Ps.begin() + i, Ps.begin() + j)); } } // O(n) void repart() { vector<int> vec; for (auto &p : parts) vec.insert(vec.end(), p.Ps.begin(), p.Ps.end()); repart(vec); } // O(log(n) + S) + amortized O(n/S) void move(int x, int y) { auto &cntx = pos_cnt[x]; auto &cnty = pos_cnt[y]; if (!--cntx) { int i = upper_bound(bounds.begin(), bounds.end(), x) - bounds.begin(); parts[i].remove(x); } if (!cnty++) { int i = upper_bound(bounds.begin(), bounds.end(), y) - bounds.begin(); parts[i].put(y); if (parts[i].Ps.size() > 2*S) repart(); } } // O(n/S * log(S)) int calc() { int ans = 0; int pnt = 0; for (auto &p : parts) { auto [x, y] = p.get(pnt); //cerr << "Ps = "; //for (auto x : p.Ps) // cerr << x << ", "; //cerr << "\npnt = " << pnt << ", x = " << x << ", y = " << y << '\n'; ans += x; pnt = y; } return ans; } }; const int N = 1<<22; PartList part_list; int pos[N]; int n; void init(signed n_, signed L_, signed X[]) { n = n_; L = L_ + 1; Loop (i,0,n) pos[i] = X[i]; part_list.init(vector(pos, pos + n)); } signed update(signed i, signed y) { part_list.move(pos[i], y); pos[i] = y; return part_list.calc(); } // move = O(log(n) + S) + amortized O(n/S) // calc = O(n/S * log(S)) // q log(n) + qS + nq/S + nq/S log(S) // qS + nq/S log(S) // S^2 / log(S) = n // S = 1280
#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...