oj.uz

Submission #174559

# Submission time Handle Problem Language Result Execution time Memory
174559 2020-01-06T12:29:40 Z emil_physmath Divide and conquer (IZhO14_divide) C++17
100 / 100
 54 ms 8924 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 380 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 4 ms 760 KB Output is correct
12 Correct 4 ms 760 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 632 KB Output is correct
2 Correct 5 ms 892 KB Output is correct
3 Correct 6 ms 988 KB Output is correct
4 Correct 24 ms 4196 KB Output is correct
5 Correct 26 ms 4472 KB Output is correct
6 Correct 54 ms 8924 KB Output is correct
7 Correct 41 ms 7672 KB Output is correct
8 Correct 43 ms 7928 KB Output is correct
9 Correct 41 ms 7544 KB Output is correct
10 Correct 43 ms 7544 KB Output is correct
11 Correct 49 ms 8028 KB Output is correct
12 Correct 52 ms 8184 KB Output is correct