Submission #174559

#	Time	Username	Problem	Language	Result	Execution time	Memory
174559		emil_physmath	Divide and conquer (IZhO14_divide)	C++17	100 / 100	54 ms	8924 KiB

divide

#include <iostream>
#include <vector>
using namespace std;
typedef long long llong;

llong t[400000];

void Build(const vector<llong>& a, int v, int vl, int vr)
{
    if (vl == vr)
    {
        t[v] = a[vr];
        return;
    }
    int vm = (vl + vr) / 2;
    Build(a, v * 2, vl, vm);
    Build(a, v * 2 + 1, vm + 1, vr);
    t[v] = min(t[v * 2], t[v * 2 + 1]);
}
int Query(int v, int vl, int vr, llong val)
{
    if (vl == vr)
        return t[v] <= val ? vr : -1;
    int vm = (vl + vr) / 2;
    if (t[v * 2] > val)
        return Query(v * 2 + 1, vm + 1, vr, val);
    return Query(v * 2, vl, vm, val);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    vector<int> x(n), g(n), e(n);
    vector<llong> ePref(n), gPref(n), val(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> x[i] >> g[i] >> e[i];
        ePref[i] = e[i] + (i ? ePref[i - 1] : 0);
        gPref[i] = g[i] + (i ? gPref[i - 1] : 0);
        val[i] = (i ? ePref[i - 1] : 0) - x[i];
    }
    Build(val, 1, 0, n - 1);
    llong ans = 0;
    for (int i = 0; i < n; ++i)
    {
        int l = Query(1, 0, n - 1, ePref[i] - x[i]);
        if (l <= i)
            ans = max(ans, gPref[i] - (l ? gPref[l - 1] : 0));
    }
    cout << ans;
}

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