Submission #344679

#	Time	Username	Problem	Language	Result	Execution time	Memory
344679		_zheksenov	Divide and conquer (IZhO14_divide)	C++14	100 / 100	59 ms	5100 KiB

divide

#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] - x[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: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52