Submission #1067023

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067023		manhlinh1501	Bigger segments (IZhO19_segments)	C++17	37 / 100	256 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 = 6e14 + 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(cur -> left == nullptr) cur -> left = new node();
        if(cur -> right == nullptr) cur -> right = new node();

        if(p <= m)
            update(cur -> left, l, m, p, x);
        else
            update(cur -> right, m + 1, r, p, x);

        cur -> x = combine(cur -> left -> 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];
//    for(int i = 1; i <= N; i++) {
//        for(int j = i - 1; j >= 0; j--) {
//            if(b[i] >= dp[j].first +  b[j]) {
//                dp[i] = {b[i] - b[j], dp[j].second + 1};
//                break;
//            }
//        }
//    }
//    for(int i = 1; i <= N; i++)
//        printf("%d %d %d\n", i, dp[i].first, dp[i].second);
    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});
    }
//    for(int i = 1; i <= N; i++)
//        printf("%d %d %d\n", i, dp[i].first, 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:78:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         freopen(TASK ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
segments.cpp:79:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         freopen(TASK ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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