Submission #479994

#	Time	Username	Problem	Language	Result	Execution time	Memory
479994		Dima_Borchuk	Divide and conquer (IZhO14_divide)	C++17	100 / 100	193 ms	35320 KiB

divide

#pragma GCC optimize("Ofast")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) int32_t(x.size())
#define pii pair < int, int >
#include <bits/stdc++.h>
#define ld long double
#define ll long long
#define _ << ' ' <<
#define se second
#define fi first
#define int ll

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

mt19937 gen(chrono::system_clock::now().time_since_epoch().count());

const int mod = (int)1e9 + 9;
const int N = (int)1e6 + 5;
const int INF = (int)1e16 + 5;

struct point {
    int x, g, e;
};

struct segmentTree {
    vector < int > t;
    int s = 1;

    void build(int n) {
        t.resize(4 * n, INF);
        while (s < n) {
            s *= 2;
        }
    }

    int getMin(int v, int vl, int vr, int l, int r) {
        if (vl > r || vr < l) {
            return INF;
        }
        if (vl >= l && vr <= r) {
            return t[v];
        }

        int mid = (vl + vr) / 2;
        return min(getMin(v * 2, vl, mid, l, r), getMin(v * 2 + 1, mid + 1, vr, l, r));
    }

    void upd(int v, int vl, int vr, int pos, int x) {
        if (vl == vr) {
            t[v] = min(t[v], x);
            return;
        }

        int mid = (vl + vr) / 2;
        if (pos <= mid) {
            upd(v * 2, vl, mid, pos, x);
        }
        else {
            upd(v * 2 + 1, mid + 1, vr, pos, x);
        }
        t[v] = min(t[v * 2], t[v * 2 + 1]);
    }

    int getMin(int l, int r) {
        return getMin(1, 1, s, l, r);
    }

    void upd(int pos, int x) {
        upd(1, 1, s, pos, x);
    }
};

int32_t main() {
    #ifdef LOCAL
//        freopen("input.txt", "r", stdin);
//        freopen("output.txt", "w", stdout);
    #endif // LOCAL

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

    int n;
    cin >> n;
    vector < point > a(n + 1);
    vector < int > pe(n + 1, 0), pg(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i].x >> a[i].g >> a[i].e;
        pe[i] = pe[i - 1] + a[i].e;
        pg[i] = pg[i - 1] + a[i].g;
    }

    set < int > all;
    map < int, int > mp;

    for (int i = 1; i <= n; i++) {
        all.insert(a[i].x - pe[i]);
        all.insert(a[i].x - pe[i - 1]);
    }
    int k = 0;
    for (auto i : all) {
        mp[i] = k++;
    }

    int ans = 0;
    segmentTree t;
    t.build(k);
    for (int i = 1; i <= n; i++) {
        t.upd(mp[a[i].x - pe[i - 1]], pg[i - 1]);
        ans = max(ans, pg[i] - t.getMin(mp[a[i].x - pe[i]], k));
    }

    cout << ans << '\n';
    return 0;
}

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52