Submission #37769

#	Time	Username	Problem	Language	Result	Execution time	Memory
37769		Talant	Divide and conquer (IZhO14_divide)	C++14	100 / 100	496 ms	56704 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 ll N = (ll)1e6 + 7;

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

void build (ll v = 1,ll tl = 1,ll tr = n) {
        if (tl == tr)
                t[v] = a[tl];
        else {
                ll 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 (ll l,ll r,ll v = 1,ll tl = 1,ll tr = n) {
        if (r < tl || l > tr)
                return -inf;
        if (l <= tl && tr <= r)
                return t[v];

        ll 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 (ll 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 (ll i = 1; i <= n; i ++) {
                ll l = i,r = n;

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

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

                mx = max(mx,res[l] - res[i - 1]);
        }

        cout << mx << endl;
}

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