oj.uz

Submission #678144

# Submission time Handle Problem Language Result Execution time Memory
678144 2023-01-05T08:53:35 Z Alcabel Bigger segments (IZhO19_segments) C++17
100 / 100
 127 ms 35276 KB 
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18;

struct SegTree {
    int n;
    long long st[1 << 21];
    SegTree() {}
    SegTree(int _n) {
        if (_n == 1) {
            n = 1;
        } else {
            n = (1 << (31 - __builtin_clz(_n - 1) + 1));
        }
        for (int i = 0; i < 2 * n; ++i) {
            st[i] = inf;
        }
    }
    void assign(int v, int tl, int tr, int i, long long val) {
        if (tl + 1 == tr) {
            st[v] = val;
            return;
        }
        int m = tl + (tr - tl) / 2;
        if (i < m) {
            assign(2 * v, tl, m, i, val);
        } else {
            assign(2 * v + 1, m, tr, i, val);
        }
        st[v] = min(st[2 * v], st[2 * v + 1]);
    }
    void assign(int i, long long val) {
        assign(1, 0, n, i, val);
    }
    int getRightmost(int v, int tl, int tr, long long val) {
        if (tl + 1 == tr) {
            return tl;
        }
        int m = tl + (tr - tl) / 2;
        if (st[2 * v + 1] <= val) {
            return getRightmost(2 * v + 1, m, tr, val);
        }
        return getRightmost(2 * v, tl, m, val);
    }
    int getRightmost(long long val) {
        return getRightmost(1, 0, n, val);
    }
    ~SegTree() {}
};

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<long long> pref(n + 1);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        pref[i + 1] = pref[i] + a[i];
    }
    vector<pair<int, long long>> f(n + 1);
    f[0] = {0, 0};
    SegTree st(n + 1);
    st.assign(0, 0);
    for (int i = 1; i <= n; ++i) {
        int j = st.getRightmost(pref[i]);
        // cerr << "i: " << i << ", j: " << j << '\n';
        f[i] = {f[j].first + 1, pref[i] - pref[j]};
        st.assign(i, pref[i] + f[i].second);
    }
    cout << f[n].first << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16724 KB Output is correct
2 Correct 7 ms 16596 KB Output is correct
3 Correct 8 ms 16680 KB Output is correct
4 Correct 7 ms 16720 KB Output is correct
5 Correct 7 ms 16688 KB Output is correct
6 Correct 7 ms 16724 KB Output is correct
7 Correct 7 ms 16704 KB Output is correct
8 Correct 7 ms 16724 KB Output is correct
9 Correct 7 ms 16724 KB Output is correct
10 Correct 7 ms 16724 KB Output is correct
11 Correct 7 ms 16724 KB Output is correct
12 Correct 7 ms 16724 KB Output is correct
13 Correct 7 ms 16724 KB Output is correct
14 Correct 7 ms 16624 KB Output is correct
15 Correct 7 ms 16724 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16724 KB Output is correct
2 Correct 7 ms 16596 KB Output is correct
3 Correct 8 ms 16680 KB Output is correct
4 Correct 7 ms 16720 KB Output is correct
5 Correct 7 ms 16688 KB Output is correct
6 Correct 7 ms 16724 KB Output is correct
7 Correct 7 ms 16704 KB Output is correct
8 Correct 7 ms 16724 KB Output is correct
9 Correct 7 ms 16724 KB Output is correct
10 Correct 7 ms 16724 KB Output is correct
11 Correct 7 ms 16724 KB Output is correct
12 Correct 7 ms 16724 KB Output is correct
13 Correct 7 ms 16724 KB Output is correct
14 Correct 7 ms 16624 KB Output is correct
15 Correct 7 ms 16724 KB Output is correct
16 Correct 7 ms 16724 KB Output is correct
17 Correct 7 ms 16724 KB Output is correct
18 Correct 7 ms 16724 KB Output is correct
19 Correct 7 ms 16724 KB Output is correct
20 Correct 7 ms 16724 KB Output is correct
21 Correct 7 ms 16724 KB Output is correct
22 Correct 9 ms 16724 KB Output is correct
23 Correct 8 ms 16732 KB Output is correct
24 Correct 7 ms 16724 KB Output is correct
25 Correct 7 ms 16724 KB Output is correct
26 Correct 7 ms 16724 KB Output is correct
27 Correct 7 ms 16724 KB Output is correct
28 Correct 7 ms 16672 KB Output is correct
29 Correct 7 ms 16636 KB Output is correct
30 Correct 7 ms 16732 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16724 KB Output is correct
2 Correct 7 ms 16596 KB Output is correct
3 Correct 8 ms 16680 KB Output is correct
4 Correct 7 ms 16720 KB Output is correct
5 Correct 7 ms 16688 KB Output is correct
6 Correct 7 ms 16724 KB Output is correct
7 Correct 7 ms 16704 KB Output is correct
8 Correct 7 ms 16724 KB Output is correct
9 Correct 7 ms 16724 KB Output is correct
10 Correct 7 ms 16724 KB Output is correct
11 Correct 7 ms 16724 KB Output is correct
12 Correct 7 ms 16724 KB Output is correct
13 Correct 7 ms 16724 KB Output is correct
14 Correct 7 ms 16624 KB Output is correct
15 Correct 7 ms 16724 KB Output is correct
16 Correct 7 ms 16724 KB Output is correct
17 Correct 7 ms 16724 KB Output is correct
18 Correct 7 ms 16724 KB Output is correct
19 Correct 7 ms 16724 KB Output is correct
20 Correct 7 ms 16724 KB Output is correct
21 Correct 7 ms 16724 KB Output is correct
22 Correct 9 ms 16724 KB Output is correct
23 Correct 8 ms 16732 KB Output is correct
24 Correct 7 ms 16724 KB Output is correct
25 Correct 7 ms 16724 KB Output is correct
26 Correct 7 ms 16724 KB Output is correct
27 Correct 7 ms 16724 KB Output is correct
28 Correct 7 ms 16672 KB Output is correct
29 Correct 7 ms 16636 KB Output is correct
30 Correct 7 ms 16732 KB Output is correct
31 Correct 7 ms 16724 KB Output is correct
32 Correct 8 ms 16724 KB Output is correct
33 Correct 8 ms 16740 KB Output is correct
34 Correct 8 ms 16724 KB Output is correct
35 Correct 8 ms 16740 KB Output is correct
36 Correct 8 ms 16724 KB Output is correct
37 Correct 7 ms 16724 KB Output is correct
38 Correct 7 ms 16732 KB Output is correct
39 Correct 8 ms 16724 KB Output is correct
40 Correct 8 ms 16832 KB Output is correct
41 Correct 8 ms 16724 KB Output is correct
42 Correct 8 ms 16724 KB Output is correct
43 Correct 8 ms 16740 KB Output is correct
44 Correct 8 ms 16744 KB Output is correct
45 Correct 8 ms 16720 KB Output is correct

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16724 KB Output is correct
2 Correct 7 ms 16596 KB Output is correct
3 Correct 8 ms 16680 KB Output is correct
4 Correct 7 ms 16720 KB Output is correct
5 Correct 7 ms 16688 KB Output is correct
6 Correct 7 ms 16724 KB Output is correct
7 Correct 7 ms 16704 KB Output is correct
8 Correct 7 ms 16724 KB Output is correct
9 Correct 7 ms 16724 KB Output is correct
10 Correct 7 ms 16724 KB Output is correct
11 Correct 7 ms 16724 KB Output is correct
12 Correct 7 ms 16724 KB Output is correct
13 Correct 7 ms 16724 KB Output is correct
14 Correct 7 ms 16624 KB Output is correct
15 Correct 7 ms 16724 KB Output is correct
16 Correct 7 ms 16724 KB Output is correct
17 Correct 7 ms 16724 KB Output is correct
18 Correct 7 ms 16724 KB Output is correct
19 Correct 7 ms 16724 KB Output is correct
20 Correct 7 ms 16724 KB Output is correct
21 Correct 7 ms 16724 KB Output is correct
22 Correct 9 ms 16724 KB Output is correct
23 Correct 8 ms 16732 KB Output is correct
24 Correct 7 ms 16724 KB Output is correct
25 Correct 7 ms 16724 KB Output is correct
26 Correct 7 ms 16724 KB Output is correct
27 Correct 7 ms 16724 KB Output is correct
28 Correct 7 ms 16672 KB Output is correct
29 Correct 7 ms 16636 KB Output is correct
30 Correct 7 ms 16732 KB Output is correct
31 Correct 7 ms 16724 KB Output is correct
32 Correct 8 ms 16724 KB Output is correct
33 Correct 8 ms 16740 KB Output is correct
34 Correct 8 ms 16724 KB Output is correct
35 Correct 8 ms 16740 KB Output is correct
36 Correct 8 ms 16724 KB Output is correct
37 Correct 7 ms 16724 KB Output is correct
38 Correct 7 ms 16732 KB Output is correct
39 Correct 8 ms 16724 KB Output is correct
40 Correct 8 ms 16832 KB Output is correct
41 Correct 8 ms 16724 KB Output is correct
42 Correct 8 ms 16724 KB Output is correct
43 Correct 8 ms 16740 KB Output is correct
44 Correct 8 ms 16744 KB Output is correct
45 Correct 8 ms 16720 KB Output is correct
46 Correct 27 ms 19540 KB Output is correct
47 Correct 27 ms 19928 KB Output is correct
48 Correct 29 ms 20192 KB Output is correct
49 Correct 30 ms 20332 KB Output is correct
50 Correct 31 ms 20428 KB Output is correct
51 Correct 30 ms 20440 KB Output is correct
52 Correct 18 ms 18484 KB Output is correct
53 Correct 13 ms 17776 KB Output is correct
54 Correct 25 ms 19716 KB Output is correct
55 Correct 30 ms 20428 KB Output is correct
56 Correct 27 ms 19932 KB Output is correct
57 Correct 30 ms 19824 KB Output is correct
58 Correct 29 ms 19852 KB Output is correct
59 Correct 28 ms 19964 KB Output is correct
60 Correct 27 ms 20052 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16724 KB Output is correct
2 Correct 7 ms 16596 KB Output is correct
3 Correct 8 ms 16680 KB Output is correct
4 Correct 7 ms 16720 KB Output is correct
5 Correct 7 ms 16688 KB Output is correct
6 Correct 7 ms 16724 KB Output is correct
7 Correct 7 ms 16704 KB Output is correct
8 Correct 7 ms 16724 KB Output is correct
9 Correct 7 ms 16724 KB Output is correct
10 Correct 7 ms 16724 KB Output is correct
11 Correct 7 ms 16724 KB Output is correct
12 Correct 7 ms 16724 KB Output is correct
13 Correct 7 ms 16724 KB Output is correct
14 Correct 7 ms 16624 KB Output is correct
15 Correct 7 ms 16724 KB Output is correct
16 Correct 7 ms 16724 KB Output is correct
17 Correct 7 ms 16724 KB Output is correct
18 Correct 7 ms 16724 KB Output is correct
19 Correct 7 ms 16724 KB Output is correct
20 Correct 7 ms 16724 KB Output is correct
21 Correct 7 ms 16724 KB Output is correct
22 Correct 9 ms 16724 KB Output is correct
23 Correct 8 ms 16732 KB Output is correct
24 Correct 7 ms 16724 KB Output is correct
25 Correct 7 ms 16724 KB Output is correct
26 Correct 7 ms 16724 KB Output is correct
27 Correct 7 ms 16724 KB Output is correct
28 Correct 7 ms 16672 KB Output is correct
29 Correct 7 ms 16636 KB Output is correct
30 Correct 7 ms 16732 KB Output is correct
31 Correct 7 ms 16724 KB Output is correct
32 Correct 8 ms 16724 KB Output is correct
33 Correct 8 ms 16740 KB Output is correct
34 Correct 8 ms 16724 KB Output is correct
35 Correct 8 ms 16740 KB Output is correct
36 Correct 8 ms 16724 KB Output is correct
37 Correct 7 ms 16724 KB Output is correct
38 Correct 7 ms 16732 KB Output is correct
39 Correct 8 ms 16724 KB Output is correct
40 Correct 8 ms 16832 KB Output is correct
41 Correct 8 ms 16724 KB Output is correct
42 Correct 8 ms 16724 KB Output is correct
43 Correct 8 ms 16740 KB Output is correct
44 Correct 8 ms 16744 KB Output is correct
45 Correct 8 ms 16720 KB Output is correct
46 Correct 27 ms 19540 KB Output is correct
47 Correct 27 ms 19928 KB Output is correct
48 Correct 29 ms 20192 KB Output is correct
49 Correct 30 ms 20332 KB Output is correct
50 Correct 31 ms 20428 KB Output is correct
51 Correct 30 ms 20440 KB Output is correct
52 Correct 18 ms 18484 KB Output is correct
53 Correct 13 ms 17776 KB Output is correct
54 Correct 25 ms 19716 KB Output is correct
55 Correct 30 ms 20428 KB Output is correct
56 Correct 27 ms 19932 KB Output is correct
57 Correct 30 ms 19824 KB Output is correct
58 Correct 29 ms 19852 KB Output is correct
59 Correct 28 ms 19964 KB Output is correct
60 Correct 27 ms 20052 KB Output is correct
61 Correct 95 ms 32324 KB Output is correct
62 Correct 99 ms 32448 KB Output is correct
63 Correct 105 ms 32716 KB Output is correct
64 Correct 121 ms 34880 KB Output is correct
65 Correct 125 ms 35276 KB Output is correct
66 Correct 127 ms 35276 KB Output is correct
67 Correct 101 ms 31688 KB Output is correct
68 Correct 54 ms 24144 KB Output is correct
69 Correct 102 ms 31484 KB Output is correct
70 Correct 124 ms 35268 KB Output is correct
71 Correct 113 ms 32464 KB Output is correct
72 Correct 106 ms 32704 KB Output is correct
73 Correct 112 ms 33388 KB Output is correct
74 Correct 119 ms 33724 KB Output is correct
75 Correct 119 ms 33724 KB Output is correct