Submission #331871

#	Time	Username	Problem	Language	Result	Execution time	Memory
331871		vitkishloh228	Divide and conquer (IZhO14_divide)	C++14	100 / 100	233 ms	20144 KiB

divide

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define int long long
vector<int> t;
int getmin(int v, int tl, int tr, int l, int r) {
    if (tl > tr || l > r) return 1e15;
    if (tl == l && tr == r) return t[v];
    int tm = (tl + tr) >> 1;
    return min(getmin(2 * v, tl, tm, l, min(r, tm)), getmin(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
}
void upd(int v, int tl, int tr, int x, int pos) {
    if (tl == tr) {
        t[v] = min(t[v], x);
        return;
    }
    int tm = (tl + tr) >> 1;
    if (pos <= tm) {
        upd(2 * v, tl, tm, x, pos);
    }
    else upd(2 * v + 1, tm + 1, tr, x, pos);
    t[v] = min(t[2 * v], t[2 * v + 1]);
}
int32_t main() {
    
    int n;
    cin >> n;
    vector<vector<int>> a;
    for (int i = 0; i < n; ++i) {
        int x, g, e;
        cin >> x >> g >> e;
        a.push_back({ x,g,e });
    }
    vector<int> pr(n + 1);
    for (int i = 0; i < n; ++i) {
        pr[i + 1] = pr[i] + a[i][2];
    }
    vector<int> pr_gold(n + 1);
    for (int i = 0; i < n; ++i) {
        pr_gold[i + 1] = pr_gold[i] + a[i][1];
    }
    vector<int> coord;
    for (int i = 0; i < n; ++i) {
        coord.push_back(pr[i] - a[i][0]);
        coord.push_back(pr[i + 1] - a[i][0]);
    }
    sort(coord.begin(), coord.end());
    coord.erase(unique(coord.begin(), coord.end()), coord.end());
    int N = coord.size();
    t.resize(4 * N, 1e15);
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        if (i == 0) {
            ans = max(ans, a[i][1]);
            int pos = lower_bound(coord.begin(), coord.end(), pr[i] - a[i][0]) - coord.begin();
            upd(1, 0, N - 1, pr_gold[i], pos);
        }
        else {
            int pos = lower_bound(coord.begin(), coord.end(), pr[i + 1] - a[i][0]) - coord.begin();
            int x = getmin(1, 0, N - 1, 0, pos);
            ans = max(ans, pr_gold[i + 1] - x);
            ans = max(ans, a[i][1]);
            pos = lower_bound(coord.begin(), coord.end(), pr[i] - a[i][0]) - coord.begin();
            upd(1, 0, N - 1, pr_gold[i], pos);
        }
    }
    cout << ans;
}

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