Submission #1067062

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067062		manhlinh1501	Bigger segments (IZhO19_segments)	C++17	73 / 100	425 ms	262144 KiB

segments

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int MAXN = 5e5 + 5;
using pli = pair<i64, int>;
const i64 oo64 = 5e14 + 5;

#define left ___left
#define right ___right

struct node {
    pli x = {0, 0};
    node *left = nullptr, *right = nullptr;

    node(pli x = {0, 0}, node *left = nullptr, node *right = nullptr) : x(x), left(left), right(right) {}
};

pli combine(const pli a, const pli b) {
    if(a.second > b.second)
        return a;
    if(a.second < b.second)
        return b;
    return {max(a.first, b.first), a.second};
}

struct segment_tree {
    node *root = new node();

    void update(node *cur, i64 l, i64 r, i64 p, pli x) {
        if(r < p or l > p) return;
        if(l == r) {
            cur -> x = combine(cur -> x, x);
            return;
        }
        i64 m = (l + r) / 2;


        if(p <= m) {
            if(cur -> left == nullptr) cur -> left = new node();
            update(cur -> left, l, m, p, x);
        } else {
            if(cur -> right == nullptr) cur -> right = new node();
            update(cur -> right, m + 1, r, p, x);
        }
        cur -> x = {0, 0};
        if(cur -> left != nullptr)
            cur -> x = combine(cur -> x, cur -> left -> x);
        if(cur -> right != nullptr)
            cur -> x = combine(cur -> x, cur -> right -> x);
    }

    pli get(node *cur, i64 l, i64 r, i64 u, i64 v) {
        if(r < u or l > v) return {0, 0};
        if(u <= l and r <= v) return cur -> x;
        i64 m = (l + r) / 2;
        pli res = {0, 0};
        if(cur -> left != nullptr)
            res = combine(res, get(cur -> left, l, m, u, v));
        if(cur -> right != nullptr)
            res = combine(res, get(cur -> right, m + 1, r, u, v));
        return res;
    }

    void update(i64 p, pli x) {
        return update(root, 1, oo64, p, x);
    }

    pli get(i64 l, i64 r) {
        return get(root, 1, oo64, l, r);
    }
} ST;

int N;
int a[MAXN];
i64 b[MAXN];
pli dp[MAXN];

signed main() {
#define TASK "code"

    if (fopen(TASK ".inp", "r")) {
        freopen(TASK ".inp", "r", stdin);
        freopen(TASK ".out", "w", stdout);
    }

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    for(int i = 1; i <= N; i++) cin >> a[i];
    for(int i = 1; i <= N; i++) b[i] = b[i - 1] + a[i];
    ST.update(0, {0, 0});
    for(int i = 1; i <= N; i++) {
        pli res = ST.get(0, b[i]);
        dp[i] = {b[i] - res.first, res.second + 1};
        ST.update(dp[i].first + b[i], {b[i], dp[i].second});
    }
    cout << dp[N].second;
    return (0 ^ 0);
}

/**
4
2 3 1 7
**/

/**
5
6 2 3 9 13
**/

/**
3
3 1 2
**/

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:82:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         freopen(TASK ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
segments.cpp:83:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         freopen(TASK ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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