Submission #37401

#	Time	Username	Problem	Language	Result	Execution time	Memory
37401		HardNut	Divide and conquer (IZhO14_divide)	C++14	100 / 100	386 ms	6864 KiB

divide

#include<iostream>
#include<cstdio>

using namespace std;

const int N = 1e5 + 5;

typedef long long ll;

ll ans, n, x[N], g[N], e[N];
ll t[N];
ll dpp[N], dp[N];

void build(int v, int L, int R) {
    if (L == R) {
        t[v] =  dpp[L - 1] - x[L];
        return;
    }
    int md = (L + R) >> 1;
    build(v * 2, L, md);
    build(v * 2 + 1, md + 1, R);
    t[v] = min(t[v * 2], t[v * 2 + 1]);
}

ll get(int v, int L, int R, int l, int r) {
    if (L > r || l > R)
        return 1e9 + 5;
    if (l <= L && R <= r)
        return t[v];
    int md = (L + R) >> 1;
    return min(get(v * 2, L, md, l, r), get(v * 2 + 1, md + 1, R, l, r));
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> g[i] >> e[i];
        dp[i] = dp[i - 1] + g[i];
        dpp[i] = dpp[i - 1] + e[i];
    }
    build(1, 1, n);
    for (int i = 1; i <= n; i++) {
        int l = 0, r = i;
        while (r - l > 1) {
            int md = (l + r) >> 1;
            if (get(1, 1, n, 1, md) <= dpp[i] - x[i]) {
                r = md;
            } else {
                l = md;
            }
        }
        ans = max(ans, dp[i] - dp[r - 1]);
    }
    cout << ans;
}

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