제출 #1076950

#제출 시각아이디문제언어결과실행 시간메모리
1076950bleahbleahTortoise (CEOI21_tortoise)C++17
0 / 100
17 ms25132 KiB
#include <bits/stdc++.h> using namespace std; #define _ << " " << const int MAXN = 5e5 + 5; const int off = 1 << 19; const int inf = 1e9; int a[MAXN]; int l[MAXN]; int r[MAXN]; int before[MAXN]; unordered_map<int, int> specialChair; typedef pair<int, int> pii; bool possible(multiset<int> s) { int last = -1, timer = 0; for(auto x : s) { if(last == -1) { timer += x - 1; } else { if(l[last] != l[x] || r[last] != r[x]) timer += x - last; else timer += min(last - l[last] + x - l[last], r[last] - last + r[last] - x); } if(timer > 2 * (x - 1)) { return 0; } last = x; //cerr << timer << '\n'; } //cerr << '\n'; //for(auto x: s) cerr << x << ' '; cerr << '\n'; //cerr << "ok\n"; return 1; } struct Tournament { vector<int> t; vector<int> p; Tournament() { t.resize(2 * off); p.resize(2 * off); } void init() { for (int i = off; i < 2 * off; ++i) { t[i] = inf + (i - off); } for (int i = off - 1; i; i--) { t[i] = min(t[i * 2], t[i * 2 + 1]); } } void prop(int x) { if (p[x]) { t[x] += p[x]; if (x < off) { p[x * 2] += p[x]; p[x * 2 + 1] += p[x]; } p[x] = 0; } } void upd(int a, int b, int v, int x = 1, int lo = 0, int hi = off) { if (lo >= a && hi <= b) { p[x] += v; prop(x); return; } prop(x); if (lo >= b || hi <= a) return; int mi = (lo + hi) >> 1; upd(a, b, v, x * 2, lo, mi); upd(a, b, v, x * 2 + 1, mi, hi); t[x] = min(t[x * 2], t[x * 2 + 1]); } int get(int a, int b, int x = 1, int lo = 0, int hi = off) { if (lo >= b || hi <= a) return inf; prop(x); if (lo >= a && hi <= b) { return t[x]; } int mi = (lo + hi) >> 1; return min(get(a, b, x * 2, lo, mi), get(a, b, x * 2 + 1, mi, hi)); } } special, updates, tracker; void moveSpecial(int a, int b) { special.upd(a, a+1, +inf); special.upd(b, b+1, -inf); } void addSpecial(int a) { special.upd(a, a+1, -inf); } long long sum; multiset<int> TT; void solve(int x, int d, int type) { int cnt = 0; while(a[x] > 0) { TT.emplace(x); if(possible(TT)) { a[x] --; sum --; cnt ++; } else { TT.erase(TT.find(x)); break; } } } int main() { int n; cin >> n; for (int i = 0; i < n; ++i) { cin >> a[i]; if (a[i] != -1) sum += a[i]; } int tmp = -1; for (int i = 0; i < n; ++i) { if (a[i] == -1) { tmp = i; } l[i] = tmp; } tmp = -1; for (int i = n - 1; i >= 0; --i) { if (a[i] == -1) { tmp = i; } r[i] = tmp; } tmp = -1; for (int i = 0; i < n; ++i) { before[i] = tmp; if (a[i] > 0) { tmp = i; } } special.init(); tracker.init(); vector<pair<int, pii>> candidates; for (int i = 0; i < n; ++i) { if (a[i] > 0) { if (r[i] != -1) { candidates.push_back({r[i] - i, {i, 1}}); } if (l[i] != -1) { candidates.push_back({i - l[i], {i, 0}}); } } } sort(candidates.begin(), candidates.end()); for (auto candidate : candidates) { int x = candidate.second.first; int d = candidate.first; int type = candidate.second.second; solve(x, d, type); } sum =0; for (int i = 0; i < n; ++i) { cin >> a[i]; if (a[i] != -1) sum += a[i]; } cout << sum << '\n'; }
#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...