oj.uz

Submission #174554

# Submission time Handle Problem Language Result Execution time Memory
174554 2020-01-06T12:27:34 Z emil_physmath Divide and conquer (IZhO14_divide) C++17
17 / 100
 6 ms 888 KB 
#include <iostream>
#include <vector>
using namespace std;

int t[400000];

void Build(const vector<int>& 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, int 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), ePref(n), gPref(n);
    vector<int> 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);
    int 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 << endl;
}

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 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 424 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
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 3 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Incorrect 2 ms 376 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 5 ms 888 KB Output is correct
3 Incorrect 6 ms 860 KB Output isn't correct
4 Halted 0 ms 0 KB -