Submission #1231805

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231805		ericl23302	Closing Time (IOI23_closing)	C++20	21 / 100	1096 ms	33348 KiB

closing

#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 = 2;

    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] - preSum[i - 1]);

    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 (auto &i : preSum) cout << i << ' ';
    // cout << endl;

    // for (int i = 0; i < 20; ++i) cout << treeWalk(1, 1, Y - X - 1, i).first << ' ' << treeWalk(1, 1, Y - X - 1, i).second << "   ";
    // cout << endl;

    for (int left = 0; left <= X; ++left) {
        for (int right = N - 1; right >= Y; --right) {
            ll curCost = 0;
            int curRes = 2;
            for (int i = left; i < X; ++i) {
                ++curRes;
                curCost += xReach[i];
            }
            for (int i = right; i > Y; --i) {
                ++curRes;
                curCost += yReach[i];
            }

            // cout << left << ' ' << right << ' ' << curCost << ' ' << curRes << endl;

            // for (int y = Y; y >= left; --y) {
            //     if (curCost > K) break;
            //     // cout << y << ' ';
            //     ll curRemain = K - curCost;
            //     // cout << curRemain << ' ';
            //     int cnt = 0;
            //     for (int i = X + 1; i < Y; ++i) {
            //         int curNeed = xReach[i];
            //         if (y <= i) curNeed = max(0ll, xReach[i] - yReach[i]);
            //         if (curRemain < curNeed) break;
            //         curRemain -= curNeed; 
            //         ++cnt;
            //     }
            //     // 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);
            //     // cout << cnt << endl;
                
            //     res = max(res, curRes + cnt);
            //     if (y > X) curCost += yReach[y - 1], ++curRes;
            //     else if (y > left) curCost += max(0ll, yReach[y - 1] - xReach[y - 1]), ++curRes;
            // }

            for (int y = Y; y >= left; --y) {
                if (curCost > K) break;
                // cout << y << ' ';
                ll curRemain = K - curCost;
                // cout << curRemain << ' ';
                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);
                // cout << cnt << endl;
                
                res = max(res, curRes + cnt);
                if (y > X) curCost += yReach[y - 1], ++curRes;
                else if (y > left) curCost += max(0ll, yReach[y - 1] - xReach[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 = 0; i < 20; ++i) cout << treeWalk(1, 1, Y - X - 1, i).first << ' ' << treeWalk(1, 1, Y - X - 1, i).second << "   ";
                // cout << endl;
            }

            for (int i = 1; i <= 4 * N; ++i) segTree[i] = modelSeg[i], lazy[i] = modelLazy[i];
        }
    }

    return res;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 9 / 9
• Subtask 3: 12 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17