Submission #493915

#	Time	Username	Problem	Language	Result	Execution time	Memory
493915		TeaTime	Bigger segments (IZhO19_segments)	C++17	100 / 100	159 ms	49252 KiB

segments

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

typedef long long ll;
typedef long double ld;

#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

const ll SZ = 5e5 + 1000, INF = 1e9 * 1e6 + 100, LG = 20;

vector<ll> vec, pref;

ll dp[SZ], dp2[SZ];

ll seg[SZ * 4];

void upd(int v, int l, int r, int pos, ll val) {
    if (l == r - 1) {
        seg[v] = val;
    } else {
        int mid = (l + r) / 2;
        if (pos < mid) {
            upd(v * 2 + 1, l, mid, pos, val);
        } else {
            upd(v * 2 + 2, mid, r, pos, val);
        }

        seg[v] = min(seg[v * 2 + 1], seg[v * 2 + 2]);
    }
}

ll ask(int v, int l, int r, int askl, int askr) {
    if (l >= askr || askl >= r) return INF;

    if (askl <= l && r <= askr) return seg[v];

    int mid = (l + r) / 2;
    return min(ask(v * 2 + 1, l, mid, askl, askr), ask(v * 2 + 2, mid, r, askl, askr));
}

int main()
{
    fastInp;

    ll n;
    cin >> n;

    vec.resize(n);
    pref.push_back(0);
    for (auto& c : vec) cin >> c;
    for (auto c : vec) pref.push_back(pref.back() + c);

    ll mn = 0, dif = 0, a2 = 0;
    set<pair<ll, ll>> st;

    for (int i = 1; i <= n; i++) {
        mn += vec[i - 1];
        dif += vec[i - 1];

        while (st.size() > 0 && dp[(*st.begin()).second] <= pref[i] - pref[(*st.begin()).second]) {
            mn = min(mn, pref[i] - pref[(*st.begin()).second]);
            a2 = max(a2, dp2[(*st.begin()).second] + 1);
            st.erase(st.begin());
        }
        dp[i] = mn;
        dp2[i] = a2;
        st.insert({ dp[i] + dif, i });
    }

    cout << dp2[n] + 1;

    return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 10 / 10
• Subtask 4: 36 / 36
• Subtask 5: 27 / 27