oj.uz

Submission #344678

# Submission time Handle Problem Language Result Execution time Memory
344678 2021-01-06T07:38:09 Z _zheksenov Divide and conquer (IZhO14_divide) C++17
0 / 100
 1 ms 492 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

typedef long long ll;

const int N = 1e6 + 7;

int t[N << 2], g[N], x[N], d[N];

void modify(int pos, int val, int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = val;
        return;
    }  
    int mid = (tl + tr) >> 1;
    if (pos <= mid) {
        modify(pos, val, v << 1, tl, mid);
    } else {
        modify(pos, val, v << 1 | 1, mid + 1, tr);
    }
    t[v] = max(t[v << 1], t[v << 1 | 1]);
}

int kth(int v, int tl, int tr, int k) {
    if (tl == tr)
        return tl;
    int mid = (tl + tr) >> 1;
    if (k <= t[v << 1 | 1]) {
        return kth(v << 1 | 1, mid + 1, tr, k);
    } else { 
        return kth(v << 1, tl, mid, k);
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);    
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int b, c;
        cin >> x[i] >> b >> c;
        d[i] = d[i - 1] + c;
        g[i] = g[i - 1] + b;
        modify(i, d[i] - d[i], 1, 1, n);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int get = kth(1, 1, n, d[i - 1] - x[i]);
        ans = max(ans, g[get] - g[i - 1]);
    }
    cout << ans << "\n";   
    return 0;
}

Subtask #1
0 / 17.0

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

Subtask #2
0 / 31.0

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

Subtask #3
0 / 52.0

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