제출 #90662

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
90662		popovicirobert	금 캐기 (IZhO14_divide)	C++14	100 / 100	229 ms	98448 KiB

divide

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44

using namespace std;

const int MAXN = (int) 1e5 + 5;

int x[MAXN + 1];
ll g[MAXN + 1], d[MAXN + 1];

struct SegTree {
    SegTree *st, *dr;
    int pos;
    SegTree() {
        st = dr = NULL;
        pos = MAXN;
    }
}*root = new SegTree;

inline void refresh(SegTree *nod) {
    nod -> pos = MAXN;
    if(nod -> st != NULL) nod -> pos = nod -> st -> pos;
    if(nod -> dr != NULL) nod -> pos = min(nod -> pos, nod -> dr -> pos);
}

void update(SegTree *nod, ll left, ll right, ll pos, int val) {
    if(left == right) {
        nod -> pos = min(nod -> pos, val);
    }
    else {
        ll mid = (left + right) / 2;
        if(pos <= mid) {
            if(nod -> st == NULL) nod -> st = new SegTree;
            update(nod -> st, left, mid, pos, val);
        }
        else {
            if(nod -> dr == NULL) nod -> dr = new SegTree;
            update(nod -> dr, mid + 1, right, pos, val);
        }
        refresh(nod);
    }
}

int query(SegTree *nod, ll left, ll right, ll l, ll r) {
    if(nod == NULL)
        return MAXN;
    if(l <= left && right <= r) {
        return nod -> pos;
    }
    else {
        ll mid = (left + right) / 2;
        int ans = MAXN;
        if(l <= mid) ans = min(ans, query(nod -> st, left, mid, l, r));
        if(mid < r) ans = min(ans, query(nod -> dr, mid + 1, right, l, r));
        return ans;
    }
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for(i = 1; i <= n; i++) {
        cin >> x[i] >> g[i] >> d[i];
        d[i] += d[i - 1];
        g[i] += g[i - 1];
    }
    g[MAXN] = 1e18;
    ll ans = 0;
    for(i = 1; i <= n; i++) {
        update(root, 0, 2e14, x[i] - d[i - 1] + 1e14, i);
        ans = max(ans, g[i] - g[query(root, 0, 2e14, x[i] - d[i] + 1e14, 2e14) - 1]);
    }
    cout << ans;
    //cin.close();
    //cout.close();
    return 0;
}

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