제출 #1346739

#제출 시각아이디문제언어결과실행 시간메모리
1346739kawhiet금 캐기 (IZhO14_divide)C++20
100 / 100
22 ms7400 KiB

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...) 47
#endif

#define int long long

constexpr int inf = 1e18;

struct SegmentTree {
    int n;
    vector<int> t;

    SegmentTree(int _n) {
        n = _n;
        t.assign(4 * n, inf);
    }

    int merge(int x, int y) {
        return min(x, y);
    }

    void update(int id, int tl, int tr, int i, int v) {
        if (tl == tr) {
            t[id] = v;
            return;
        }
        int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1;
        if (i <= tm) {
            update(x, tl, tm, i, v);
        } else {
            update(y, tm + 1, tr, i, v);
        }
        t[id] = merge(t[x], t[y]);
    }

    int get(int id, int tl, int tr, int s) {
        if (tl == tr) {
            return tl;
        }
        int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1;
        if (t[x] <= s) {
            return get(x, tl, tm, s);
        } else {
            return get(y, tm + 1, tr, s);
        }
    }

    void update(int i, int v) { update(0, 0, n - 1, i, v); }
    int get(int s) { return get(0, 0, n - 1, s); }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> x(n), g(n), d(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> g[i] >> d[i];
    }
    vector<int> p(n + 1), k(n + 1);
    for (int i = 0; i < n; i++) {
        p[i + 1] = p[i] + d[i];
        k[i + 1] = k[i] + g[i];
    }
    SegmentTree t(n);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int s = p[i + 1] - x[i];
        t.update(i, p[i] - x[i]);
        int j = t.get(s);
        ans = max(ans, k[i + 1] - k[j]);
    }
    cout << ans << '\n';
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...