Submission #840744

#	Time	Username	Problem	Language	Result	Execution time	Memory
840744		Mahtimursu	Closing Time (IOI23_closing)	C++17	35 / 100	935 ms	10828 KiB

closing

#include "closing.h"

#include <vector>

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define NN (2 << 12)

int n, x, y;
ll k;

pair<ll, int> tree[2 * NN];
ll pt[3][NN];

void st(int k, pair<ll, int> x) {
    k += NN;
    tree[k] = x;

    for (k /= 2; k >= 1; k /= 2) {
        tree[k] = {tree[2 * k].first + tree[2 * k + 1].first, tree[2 * k].second + tree[2 * k + 1].second};
    }
}

pair<ll, int> sum(int a, int b) {
    a += NN;
    b += NN;
    pair<ll, int> ans = {0, 0};
    while (a <= b) {
        if (a % 2 == 1) {
            ans.first += tree[a].first;
            ans.second += tree[a].second;
            a++;
        }
        if (b % 2 == 0) {
            ans.first += tree[b].first;
            ans.second += tree[b].second;
            b--;
        }
        a /= 2; b /= 2;
    }

    return ans;
}

ll gt(int i, int a, int b) {
    ll ans = pt[i][b];
    if (a != 0) ans -= pt[i][a - 1];
    return ans;
}

int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{

    n = N;
    x = X;
    y = Y;
    k = K;

    pt[0][x] = 0;
    for (int i = x - 1; i >= 0; --i) {
        pt[0][i] = W[i] + pt[0][i + 1];
    }
    for (int i = x + 1; i < n; ++i) {
        pt[0][i] = W[i - 1] + pt[0][i - 1];
    }

    pt[1][y] = 0;
    for (int i = y - 1; i >= 0; --i) {
        pt[1][i] = W[i] + pt[1][i + 1];
    }
    for (int i = y + 1; i < n; ++i) {
        pt[1][i] = W[i - 1] + pt[1][i - 1];
    }

    pt[2][0] = pt[1][0];
    for (int i = 1; i < n; ++i) {
        pt[2][i] = pt[2][i - 1] + max(pt[0][i], pt[1][i]);
        pt[1][i] += pt[1][i - 1];
        pt[0][i] += pt[0][i - 1];
    }

    /*for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << pt[i][j] << " ";
        }
        cout << endl;
    }*/

    vector<pair<ll, int>> comb;

    for (int i = 0; i < x; ++i) {
        comb.push_back({gt(0, i, i), i});
    }
    for (int i = y + 1; i < n; ++i) {
        comb.push_back({gt(1, i, i), i});
    }

    sort(comb.begin(), comb.end());

    map<int, int> pos_to_idx;

    int idx = 0;
    for (auto [val, x] : comb) {
        pos_to_idx[x] = idx;
        // cout << "idx: " << idx << " id: " << x << " = " << val << endl;
        st(idx++, {val, 1});
    }
    int idx_tot = idx;

    int best = 0;

    for (int ar = x; ar < n; ++ar) {
        if (ar > y) {
            st(pos_to_idx[ar], {0, 0});
        }
        vector<pair<int, ll>> rst;
        for (int bl = y; bl >= 0; --bl) {
            ll cur = 0;
            int ans = 0;
            if (bl <= ar) {
                cur += gt(2, bl, ar);
                ans += 2 * (ar - bl + 1);
            }

            // [a, bl-1]
            int tmp = min(bl - 1, ar);
            if (x <= tmp) {
                cur += gt(0, x, tmp);
                ans += (tmp) - x + 1;
            }

            // [ar + 1, b]
            tmp = max(ar + 1, bl);
            if (tmp <= y) {
                cur += gt(1, tmp, y);
                ans += y - tmp + 1;
            }

            // too large
            if (cur > k) break;
            ll left = k - cur;

            if (bl < x) {
                int tr_i = pos_to_idx[bl];
                rst.push_back({tr_i, sum(tr_i, tr_i).first});
                st(tr_i, {0, 0});
            }

            // cout << "ar: " << ar << " bl: " << bl << " cur: " << cur << " k: " << k << " ans: " << ans << endl;

            int tk = -1;
            for (int b = 1 << 12; b >= 1; b /= 2) {
                if (tk + b < idx_tot && sum(0, tk + b).first <= left) {
                    tk += b;
                }
            }

            if (tk != -1) ans += sum(0, tk).second;

            /*int tk = 0;
            while (tk < idx_tot && left >= sum(tk, tk).first) {
                left -= sum(tk, tk).first;
                ans += sum(tk, tk).second;
                // cout << left << ", " << tk << " " << sum(tk, tk).first << " " << sum(tk, tk).second << endl;
                tk++;
            }*/

            /*int li = min(bl - 1, x - 1);
            int ri = max(ar + 1, y + 1);

            while (true) {
                ll small = k;
                int use = 0;
                if (li >= 0) {
                    small = gt(0, li, li);
                    use = 1;
                }
                if (ri < n && gt(1, ri, ri) < small) {
                    small = gt(1, ri, ri);
                    use = 2;
                }

                if (use == 0 || left < small) break;

                if (use == 1) li--;
                if (use == 2) ri++;

                left -= small;
                ans++;
            }*/
            best = max(best, ans);
        }
        for (auto [idx, val] : rst) {
            st(idx, {val, 1});
        }
    }


    return best;
}

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