oj.uz

Submission #90662

# Submission time Handle Problem Language Result Execution time Memory
90662 2018-12-23T10:28:49 Z popovicirobert Divide and conquer (IZhO14_divide) C++14
100 / 100
 229 ms 98448 KB 
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44

using namespace std;

const int MAXN = (int) 1e5 + 5;

int x[MAXN + 1];
ll g[MAXN + 1], d[MAXN + 1];

struct SegTree {
    SegTree *st, *dr;
    int pos;
    SegTree() {
        st = dr = NULL;
        pos = MAXN;
    }
}*root = new SegTree;

inline void refresh(SegTree *nod) {
    nod -> pos = MAXN;
    if(nod -> st != NULL) nod -> pos = nod -> st -> pos;
    if(nod -> dr != NULL) nod -> pos = min(nod -> pos, nod -> dr -> pos);
}

void update(SegTree *nod, ll left, ll right, ll pos, int val) {
    if(left == right) {
        nod -> pos = min(nod -> pos, val);
    }
    else {
        ll mid = (left + right) / 2;
        if(pos <= mid) {
            if(nod -> st == NULL) nod -> st = new SegTree;
            update(nod -> st, left, mid, pos, val);
        }
        else {
            if(nod -> dr == NULL) nod -> dr = new SegTree;
            update(nod -> dr, mid + 1, right, pos, val);
        }
        refresh(nod);
    }
}

int query(SegTree *nod, ll left, ll right, ll l, ll r) {
    if(nod == NULL)
        return MAXN;
    if(l <= left && right <= r) {
        return nod -> pos;
    }
    else {
        ll mid = (left + right) / 2;
        int ans = MAXN;
        if(l <= mid) ans = min(ans, query(nod -> st, left, mid, l, r));
        if(mid < r) ans = min(ans, query(nod -> dr, mid + 1, right, l, r));
        return ans;
    }
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for(i = 1; i <= n; i++) {
        cin >> x[i] >> g[i] >> d[i];
        d[i] += d[i - 1];
        g[i] += g[i - 1];
    }
    g[MAXN] = 1e18;
    ll ans = 0;
    for(i = 1; i <= n; i++) {
        update(root, 0, 2e14, x[i] - d[i - 1] + 1e14, i);
        ans = max(ans, g[i] - g[query(root, 0, 2e14, x[i] - d[i] + 1e14, 2e14) - 1]);
    }
    cout << ans;
    //cin.close();
    //cout.close();
    return 0;
}

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 500 KB Output is correct
3 Correct 2 ms 500 KB Output is correct
4 Correct 2 ms 500 KB Output is correct
5 Correct 2 ms 544 KB Output is correct
6 Correct 3 ms 544 KB Output is correct
7 Correct 2 ms 548 KB Output is correct
8 Correct 2 ms 680 KB Output is correct
9 Correct 2 ms 720 KB Output is correct
10 Correct 2 ms 720 KB Output is correct
11 Correct 2 ms 720 KB Output is correct
12 Correct 2 ms 720 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 720 KB Output is correct
2 Correct 2 ms 720 KB Output is correct
3 Correct 3 ms 860 KB Output is correct
4 Correct 3 ms 988 KB Output is correct
5 Correct 4 ms 1132 KB Output is correct
6 Correct 5 ms 1804 KB Output is correct
7 Correct 3 ms 1804 KB Output is correct
8 Correct 4 ms 1804 KB Output is correct
9 Correct 4 ms 1804 KB Output is correct
10 Correct 5 ms 1804 KB Output is correct
11 Correct 11 ms 4144 KB Output is correct
12 Correct 11 ms 4144 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4144 KB Output is correct
2 Correct 15 ms 4500 KB Output is correct
3 Correct 20 ms 7444 KB Output is correct
4 Correct 87 ms 33940 KB Output is correct
5 Correct 92 ms 33940 KB Output is correct
6 Correct 229 ms 98448 KB Output is correct
7 Correct 170 ms 98448 KB Output is correct
8 Correct 171 ms 98448 KB Output is correct
9 Correct 126 ms 98448 KB Output is correct
10 Correct 119 ms 98448 KB Output is correct
11 Correct 169 ms 98448 KB Output is correct
12 Correct 164 ms 98448 KB Output is correct