oj.uz

Submission #37769

# Submission time Handle Problem Language Result Execution time Memory
37769 2017-12-28T05:19:53 Z Talant Divide and conquer (IZhO14_divide) C++14
100 / 100
 496 ms 56704 KB 
#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.0 / 17.0

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

Subtask #2
31.0 / 31.0

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

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 56704 KB Output is correct
2 Correct 39 ms 56704 KB Output is correct
3 Correct 23 ms 56704 KB Output is correct
4 Correct 169 ms 56704 KB Output is correct
5 Correct 193 ms 56704 KB Output is correct
6 Correct 416 ms 56704 KB Output is correct
7 Correct 386 ms 56704 KB Output is correct
8 Correct 496 ms 56704 KB Output is correct
9 Correct 333 ms 56704 KB Output is correct
10 Correct 376 ms 56704 KB Output is correct
11 Correct 413 ms 56704 KB Output is correct
12 Correct 416 ms 56704 KB Output is correct