Submission #840707

#	Time	Username	Problem	Language	Result	Execution time	Memory
840707		Mahtimursu	Closing Time (IOI23_closing)	C++17	0 / 100	46 ms	10572 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;

ll tree[2 * NN];
ll pt[3][NN];

void set(int k, ll x) {
    k += NN;
    tree[k] = x;

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

ll sum(int a, int b) {
    a += NN;
    b += NN;
    ll ans = 0;
    while (a <= b) {
        if (a % 2 == 1) ans += tree[a++];
        if (b % 2 == 0) ans += tree[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;
    }

    int best = 0;

    for (int ar = x; ar < n; ++ar) {
        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;

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

            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);
        }
    }


    return best;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 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