Submission #1183467

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183467		peteza	Divide and conquer (IZhO14_divide)	C++20	100 / 100	46 ms	7320 KiB

divide

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n;
ll x[100005], g[100005], d[100005], val[100005];
ll qsg[100005];
ll ans = LLONG_MIN;

ll segm[400005];
void upd(int idx, int l, int r, int tgt, ll val) {
    if(l == r) {segm[idx] = max(segm[idx], val); return;}
    int mid = (l+r) >> 1;
    if(tgt <= mid) upd(idx*2+1, l, mid, tgt, val);
    else upd(idx*2+2, mid+1, r, tgt, val);
    segm[idx] = max(segm[idx*2+1], segm[idx*2+2]);
}

ll qr(int idx, int l, int r, int tl, int tr) {
    if(tl <= l && r <= tr) return segm[idx];
    if(tr < l || r < tl) return LLONG_MIN;
    int mid = (l+r) >> 1;
    return max(qr(idx*2+1, l, mid, tl, tr), qr(idx*2+2, mid+1, r, tl, tr));
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n;
    vector<ll> diffval;
    for(int i=1;i<=n;i++) {
        cin >> x[i] >> g[i] >> d[i];
        qsg[i] = qsg[i-1] + g[i];
        val[i] = val[i-1] + d[i] - (x[i] - x[i-1]);
        diffval.emplace_back(val[i]);
        //cout << val[i] << ' ';
    }
    sort(diffval.begin(), diffval.end());
    diffval.resize(unique(diffval.begin(), diffval.end()) - diffval.begin());
    for(int i=n;i>=1;i--) {
        int cpos = lower_bound(diffval.begin(), diffval.end(), val[i] - d[i]) - diffval.begin();
        upd(0, 0, diffval.size()-1, lower_bound(diffval.begin(), diffval.end(), val[i]) - diffval.begin(), qsg[i]); 
        ans = max(ans, qr(0, 0, diffval.size()-1, cpos, diffval.size()-1) - qsg[i-1]);
    }
    cout << ans;
}

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52