oj.uz

Submission #37765

# Submission time Handle Problem Language Result Execution time Memory
37765 2017-12-28T05:09:48 Z Talant Divide and conquer (IZhO14_divide) C++14
0 / 100
 9 ms 6312 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 int N = (int)1e5 + 7;

int n;
int x[N],g[N],d[N];
ll p[N],res[N],mx,a[N],t[N];

void build (int v = 1,int tl = 1,int tr = n) {
        if (tl == tr)
                t[v] = a[tl];
        else {
                int 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 (int l,int r,int v = 1,int tl = 1,int tr = n) {
        if (r < tl || l > tr)
                return -inf;
        if (l <= tl && tr <= r)
                return t[v];

        int 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 (int 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 (int i = 1; i <= n; i ++) {
                int l = i,r = n;

                while (r - l > 1) {
                        int m = (r + l) >> 1;

                        if (get(m,n) >= p[i - 1] - x[i])
                                l = m;
                        else
                                r = m;
                }
                mx = max(mx,res[l] - res[i - 1]);
        }

        cout << mx << endl;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6312 KB Output is correct
2 Incorrect 0 ms 6312 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 6312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 6312 KB Output isn't correct
2 Halted 0 ms 0 KB -