제출 #1231740

#제출 시각아이디문제언어결과실행 시간메모리
1231740ericl23302Closing Time (IOI23_closing)C++20
0 / 100
1096 ms33348 KiB
#include "closing.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; vector<ll> segTree(8e5), lazy(8e5); void pushDown(int cur, int left, int right) { if (!lazy[cur]) return; segTree[cur] += lazy[cur]; if (left != right) { lazy[cur * 2] += lazy[cur]; lazy[cur * 2 + 1] += lazy[cur]; } lazy[cur] = 0; } void update(int cur, int left, int right, int tLeft, int tRight, ll val) { pushDown(cur, left, right); if (tRight < left || tLeft > right) return; if (tLeft <= left && tRight >= right) { lazy[cur] = val; pushDown(cur, left, right); return; } int mid = (left + right) / 2; update(cur * 2, left, mid, tLeft, tRight, val); update(cur * 2 + 1, mid + 1, right, tLeft, tRight, val); segTree[cur] = segTree[cur * 2] + segTree[cur * 2 + 1]; } pair<ll, int> treeWalk(int cur, int left, int right, ll val) { pushDown(cur, left, right); if (val >= segTree[cur]) return {segTree[cur], right - left + 1}; if (left == right) return {0, 0}; int mid = (left + right) / 2; auto res = treeWalk(cur * 2, left, mid, val); if (val > segTree[cur * 2]) { auto res2 = treeWalk(cur * 2 + 1, mid + 1, right, val - segTree[cur * 2]); res.first += res2.first; res.second += res2.second; } return res; } int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W) { segTree.clear(); lazy.clear(); segTree.assign(8e5, 0); lazy.assign(8e5, 0); vector<ll> xReach(N, 0), yReach(N, 0); auto get = [&](int a, int b) { return W[min(a, b)]; }; auto preComp = [&] () { ll cur = 0; for (int i = X + 1; i < N; ++i) { cur += get(i - 1, i); xReach[i] = cur; } cur = 0; for (int i = X - 1; i >= 0; --i) { cur += get(i, i + 1); xReach[i] = cur; } cur = 0; for (int i = Y + 1; i < N; ++i) { cur += get(i - 1, i); yReach[i] = cur; } cur = 0; for (int i = Y - 1; i >= 0; --i) { cur += get(i, i + 1); yReach[i] = cur; } }; preComp(); int res = 0; vector<ll> preSum(Y - X); for (int i = 1; i < Y - X; ++i) preSum[i] = preSum[i - 1] + xReach[i + X], update(1, 1, Y - X - 1, i, i, preSum[i]); vector<ll> modelSeg(N * 4 + 1), modelLazy(N * 4 + 1); for (int i = 1; i <= 4 * N; ++i) modelSeg[i] = segTree[i], modelLazy[i] = lazy[i]; for (int left = 0; left <= X; ++left) { for (int right = N - 1; right >= Y; --right) { ll curCost = 0; int curRes = 0; for (int i = left; i < X; ++i) { ++curRes; curCost += xReach[i]; } for (int i = right; i > Y; --i) { ++curRes; curCost += yReach[i]; } for (int y = Y; y >= left; --y) { if (curCost > K) break; ll curRemain = K - curCost; auto [cost, cnt] = treeWalk(1, 1, Y - X - 1, curRemain); curRemain -= cost; if (cnt == Y - X - 1) cnt += min(curRemain / xReach[Y], (ll)right - Y + 1); res = max(res, curRes + cnt); if (y) curCost += yReach[y - 1], ++curRes; if (y > X + 1) update(1, 1, Y - X - 1, y - X - 1, Y - X - 1, min(xReach[y - 1], yReach[y - 1])); } for (int i = 1; i <= 4 * N; ++i) segTree[i] = modelSeg[i], lazy[i] = modelLazy[i]; } } return res + 2; }
#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...
#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...