oj.uz

Submission #840744

# Submission time Handle Problem Language Result Execution time Memory
840744 2023-08-31T16:35:21 Z Mahtimursu Closing Time (IOI23_closing) C++17
35 / 100
 935 ms 10828 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 10828 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 360 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 10 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 14 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 2 ms 332 KB Output is correct
24 Correct 2 ms 212 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 360 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 10 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 14 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 2 ms 332 KB Output is correct
24 Correct 2 ms 212 KB Output is correct
25 Correct 9 ms 496 KB Output is correct
26 Correct 713 ms 852 KB Output is correct
27 Correct 2 ms 724 KB Output is correct
28 Correct 180 ms 448 KB Output is correct
29 Correct 935 ms 596 KB Output is correct
30 Correct 2 ms 596 KB Output is correct
31 Correct 39 ms 340 KB Output is correct
32 Correct 40 ms 340 KB Output is correct

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -