oj.uz

Submission #37770

# Submission time Handle Problem Language Result Execution time Memory
37770 2017-12-28T05:20:35 Z Talant Divide and conquer (IZhO14_divide) C++14
100 / 100
 433 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 3 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 3 ms 56704 KB Output is correct
11 Correct 16 ms 56704 KB Output is correct
12 Correct 13 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 26 ms 56704 KB Output is correct
3 Correct 43 ms 56704 KB Output is correct
4 Correct 169 ms 56704 KB Output is correct
5 Correct 209 ms 56704 KB Output is correct
6 Correct 419 ms 56704 KB Output is correct
7 Correct 363 ms 56704 KB Output is correct
8 Correct 389 ms 56704 KB Output is correct
9 Correct 353 ms 56704 KB Output is correct
10 Correct 376 ms 56704 KB Output is correct
11 Correct 396 ms 56704 KB Output is correct
12 Correct 433 ms 56704 KB Output is correct