Submission #678144

#	Time	Username	Problem	Language	Result	Execution time	Memory
678144		Alcabel	Bigger segments (IZhO19_segments)	C++17	100 / 100	127 ms	35276 KiB

segments

#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 / 13
• Subtask 2: 14 / 14
• Subtask 3: 10 / 10
• Subtask 4: 36 / 36
• Subtask 5: 27 / 27