Submission #206732

#	Time	Username	Problem	Language	Result	Execution time	Memory
206732		edsa	Bigger segments (IZhO19_segments)	C++14	100 / 100	247 ms	42428 KiB

segments

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
using vii = vector<ii>;
const ll MOD = 998244353;
const int INF = 1e9+9;
const int MAXN = 1000006;

// This is a treap for searching max val of nodes with key < threshold
struct item {
    ll key;
    int prior;
    ii val, max;
    item * l, * r;
    item() { }
    item (ll key, int prior, ii val) : key(key),
      prior(prior), val(val), max(val), l(NULL), r(NULL) {}
};

void upd(item* t) {
    if (!t) return;
    t->max = t->val;
    if (t->l && t->l->max > t->max)
        t->max = t->l->max;
    if (t->r && t->r->max > t->max)
        t->max = t->r->max;
}

void split (item* t, ll key, item* & l, item* & r) {
    if (!t)
        l = r = NULL;
    else if (key < t->key)
        split (t->l, key, l, t->l),  r = t;
    else
        split (t->r, key, t->r, r),  l = t;
    upd(t);
}

void insert (item* & t, item* it) {
    if (!t)
        t = it;
    else if (it->prior > t->prior)
        split (t, it->key, it->l, it->r),  t = it;
    else
        insert (it->key < t->key ? t->l : t->r, it);
    upd(t);
}



int n, m, k, a[MAXN];
ll s[MAXN];
using il = pair<int, ll>;
il dp[MAXN];
item* root;

ii query(ll threshold) {
    // O(n) but simple implementation:
    // il ans = il(-1, 0);
    // for (int i = 0; i < MAXN; i++) {
    //     if (dp[i].second+s[i] <= threshold)
    //         ans = max(ans, il(dp[i].first, i));
    // }
    // return ans;

    ii ans(0, 0);
    item* it = root;
    while (it) {
        if (it->key > threshold) {
            it = it->l;
        } else {
            ans = max(ans, it->val);
            if (it->l)
                ans = max(ans, it->l->max);
            it = it->r;
        }
    }
    return ans;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        s[i+1] = s[i]+a[i];
    }

    dp[0] = il(0, 0);
    root = new item(0, rng(), ii(0, 0));
    for (int i = 1; i < n; i++) {
        ii maxi = query(s[i]);
        insert(root, new item(2*s[i]-s[maxi.second], rng(), ii(maxi.first+1, i)));
    }
    cout << query(s[n]).first+1 << endl;
}

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