제출 #37765

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
37765		Talant	금 캐기 (IZhO14_divide)	C++14	0 / 100	9 ms	6312 KiB

divide

#include <bits/stdc++.h>

#define fr first
#define sc second
#define OK puts("OK");
#define pb push_back
#define mk make_pair

using namespace std;

typedef long long ll;

const ll inf = (ll)1e18 + 7;
const int N = (int)1e5 + 7;

int n;
int x[N],g[N],d[N];
ll p[N],res[N],mx,a[N],t[N];

void build (int v = 1,int tl = 1,int tr = n) {
        if (tl == tr)
                t[v] = a[tl];
        else {
                int tm = (tl + tr) >> 1;

                build (v * 2,tl,tm);
                build (v * 2 + 1,tm + 1,tr);

                t[v] = max(t[v * 2],t[v * 2 + 1]);
        }
}

ll get (int l,int r,int v = 1,int tl = 1,int tr = n) {
        if (r < tl || l > tr)
                return -inf;
        if (l <= tl && tr <= r)
                return t[v];

        int tm = (tl + tr) >> 1;

        return max(get(l,r,v * 2,tl,tm),get(l,r,v * 2 + 1,tm + 1,tr));
}

int main () {
        cin >> n;

        for (int i = 1; i <= n; i ++) {
                cin >> x[i] >> g[i] >> d[i];
                p[i] = p[i - 1] + d[i];
                res[i] = res[i - 1] + g[i];
                a[i] = p[i] - x[i];
        }

        build ();

        for (int i = 1; i <= n; i ++) {
                int l = i,r = n;

                while (r - l > 1) {
                        int m = (r + l) >> 1;

                        if (get(m,n) >= p[i - 1] - x[i])
                                l = m;
                        else
                                r = m;
                }
                mx = max(mx,res[l] - res[i - 1]);
        }

        cout << mx << endl;
}

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