제출 #38309

#제출 시각아이디문제언어결과실행 시간메모리
38309romanasa등산 경로 (IZhO12_route)C++14
0 / 100
2000 ms11304 KiB
#include <bits/stdc++.h> #define err(...) fprintf(stderr, __VA_ARGS__), fflush(stderr) using namespace std; typedef long long ll; #define TASK "g" struct segment { int val, len, pos; bool operator < (const segment &b) const { return pos < b.pos; } }; set<segment> S; set<pair<int, int> > T; void calc(int pos, int mx, vector<int> &x) { int n = (int)x.size(); vector<pair<int, int> > cur; for (int i = 0; i < n; i++) { int ind = (pos + i) % n; if (cur.empty() || cur.back().first != x[ind]) cur.push_back({ x[ind], 1 }); else cur.back().second++; } for (int i = 0; i < (int)cur.size(); i++) { auto c = cur[i]; int pr = cur[i ? i - 1 : (int)cur.size() - 1].first; int nt = cur[(i + 1) % (int)cur.size()].first; S.insert({ c.first, c.second, pos }); if (c.first < pr && c.first < nt) T.insert({ c.second, pos }); pos = (pos + c.second) % n; } } void add(segment c) { auto it = S.insert(c).first; auto prv = it; if (it == S.begin()) prv = --S.end(); else --prv; auto nxt = it; if (it == --S.end()) nxt = S.begin(); else ++nxt; if (c.val < nxt->val && c.val < prv->val) T.insert({ c.len, c.pos }); } int main() { int n, k; cin >> n >> k; vector<int> x(n); for (int i = 0; i < n; i++) cin >> x[i]; int pos = -1; for (int i = 0; i < n; i++) { if (x[i] != x[(i + 1) % n]) pos = (i + 1) % n; } if (pos == -1) return 0 * puts("0"); int mx = *max_element(x.begin(), x.end()); calc(pos, mx, x); int ans = 0; //for (auto c : S) err("(%d, %d, %d), ", c.val, c.len, c.pos); err("\n"); //for (auto c : T) err("(%d, %d), ", c.first, c.second); err("\n"); while (T.size() && k >= T.begin()->first) { k -= T.begin()->first; auto it = S.lower_bound({ -1, -1, T.begin()->second }); T.erase(T.begin()); //err("(%d, %d, %d)\n", it->val, it->len, it->pos); ans += 2; if (S.size() == 1) break; auto prv = it; if (it == S.begin()) prv = --S.end(); else --prv; auto nxt = it; if (it == --S.end()) nxt = S.begin(); else ++nxt; if (prv == nxt) { if (it->val + 1 < prv->val) { auto c = *it; S.erase(it); c.val++; add(c); } else { auto c = *it; c.val++; c.len += prv->len; S.erase(it); S.erase(prv); add(c); } } else { if (it->val + 1 < prv->val && it->val + 1 < nxt->val) { auto c = *it; S.erase(it); c.val++; add(c); } else if (it->val + 1 < prv->val) { auto c = *it; c.len += nxt->len; c.val++; S.erase(it); S.erase(nxt); add(c); } else if (it->val + 1 < nxt->val) { auto c = *it; c.len += prv->len; c.pos = prv->pos; c.val++; S.erase(it); S.erase(prv); add(c); } else { auto c = *it; c.len += prv->len; c.len += nxt->len; c.pos = prv->pos; c.val++; S.erase(it); S.erase(prv); S.erase(nxt); add(c); } } //for (int i = 0; i < c.len; i++) x[(i + c.pos) % n]++; /* S.clear(); pos = -1; for (int i = 0; i < n; i++) { if (x[i] != x[(i + 1) % n]) pos = (i + 1) % n; } if (pos == -1) break; calc(pos, mx, x); */ //for (auto c : S) err("(%d, %d, %d), ", c.val, c.len, c.pos); err("\n"); } cout << ans << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...