Submission #172650

#	Time	Username	Problem	Language	Result	Execution time	Memory
172650		srvlt	Bigger segments (IZhO19_segments)	C++14	100 / 100	634 ms	52344 KiB

segments

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree <pair <int, int>, null_type, less <pair <int, int> >, rb_tree_tag, tree_order_statistics_node_update>
using namespace __gnu_pbds;

#define ll long long
#define db double
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define mp make_pair
#define size(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define low_b lower_bound

#define endl "\n"
#define int long long

using namespace std;

void dout() {
    cerr << endl;
}
template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
    cerr << H << ' ';
    dout(T...);
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair <int, int> pii;

const int N = 5e5 + 7;
int n, a[N], p[N], dp[N], opt[N];

uniform_int_distribution <int> range(0, (int)1e9);

struct Node {
    Node * l = nullptr, * r = nullptr;
    int x = 0, y = 0, key = 0, mx = -1;
    Node(int x) {
        this -> x = x;
        mx = x;
        y = range(rng);
        key = dp[x] + p[x];
    }
};

typedef Node * node;
typedef pair <node, node> Pair;

int mx(node t) {
    if (!t) {
        return -1;
    }
    return t -> mx;
}

int get(int x, int y) {
    if (x == -1) {
        return y;
    }
    if (y == -1) {
        return x;
    }
    if (p[x] > p[y]) {
        return x;
    }
    return y;
}

void upd(node t) {
    t -> mx = get(t -> x, get(mx(t -> l), mx(t -> r)));
}

node merge(node l, node r) {
    if (!l) {
        return r;
    }
    if (!r) {
        return l;
    }
    if (l -> y > r -> y) {
        l -> r = merge(l -> r, r);
        upd(l);
        return l;
    }   else {
        r -> l = merge(l, r -> l);
        upd(r);
        return r;
    }
}

Pair split(node t, int k) {
    if (!t) {
        return {nullptr, nullptr};
    }
    if (t -> key <= k) {
        Pair q = split(t -> r, k);
        t -> r = q.fi;
        upd(t);
        return {t, q.se};
    }   else {
        Pair q = split(t -> l, k);
        t -> l = q.se;
        upd(t);
        return {q.fi, t};
    }
}

node root = nullptr;

void insert(int x) {
    node p = new Node(x);
    Pair q = split(root, p -> key);
    root = merge(q.fi, merge(p, q.se));
}

int getmax(int x) {
    Pair q = split(root, x);
    int res = mx(q.fi);
    root = merge(q.fi, q.se);
    return res;
}

int ans;

void getans(int x) {
    if (x == -1) {
        return;
    }
    ans++;
    getans(opt[x]);
}

void solve(int tc) {
    // check for (int i = 0; i < n; j++)
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        p[i] = p[i - 1] + a[i];
    }
    int res;
    for (int i = 1; i <= n; i++) {
        res = getmax(p[i]);
        dp[i] = p[i];
        if (res != -1) {
            dp[i] -= p[res];
        }
        opt[i] = res;
        insert(i);
    }
    getans(n);
    cout << ans;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int tc = 1;
//    cin >> tc;
    for (int i = 0; i < tc; i++) {
        solve(i);
//        cleanup();
    }
}

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