Submission #916782

#	Time	Username	Problem	Language	Result	Execution time	Memory
916782		atom	Divide and conquer (IZhO14_divide)	C++17	100 / 100	46 ms	11168 KiB

divide

#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;

#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif

const int N = 2e5 + 5;

template <typename T>
struct FenwickTree {
    vector <T> f;
    int n;
    const T INF = 1e18 + 5;
    FenwickTree(int _n){
        init(_n);
    }
    void init(int _n) {
        n = _n;
        f.assign(n + 5, INF);
    }
    void upd(int x, ll val) {
        for (; x <= n; x += x & (-x))
            f[x] = min(f[x], val);
    }
    T qry(int x) {
        T ans = INF;
        for (; x > 0; x -= x & (-x))
            ans = min(ans, f[x]);
        return ans;
    }
};

int n;
int x[N], g[N], e[N];
ll prfE[N], prfG[N], dp[N];

signed main() {
    cin.tie(0) -> sync_with_stdio(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> x[i] >> g[i] >> e[i];

    vector <ll> vals;
    for (int i = 1; i <= n; ++i) {
        prfG[i] = prfG[i - 1] + g[i];
        prfE[i] = prfE[i - 1] + e[i];
        vals.push_back(prfE[i] - x[i]);
        vals.push_back(prfE[i - 1] - x[i]);
        // xi - xj <= fe(i) - fe(j - 1) -> fe(i) - xi >= fe(j - 1) - xj
        // dp(i) = dp(j) + f(j + 1, i) = f(i) + max(dp(j) - f(j));
    }

    sort(vals.begin(), vals.end());
    vals.resize(unique(vals.begin(), vals.end()) - vals.begin());

    auto get = [&] (ll tar) {
        return (int) (lower_bound(vals.begin(), vals.end(), tar) - vals.begin() + 1);
    };

    FenwickTree <ll> fen((int) vals.size());
    for (int i = 1; i <= n; ++i) {
        ll p = get(prfE[i] - x[i]);
        dp[i] = max(1LL * g[i], prfG[i] - fen.qry(p));
        ll _p = get(prfE[i - 1] - x[i]); 
        fen.upd(_p, prfG[i - 1]);
    }
    cout << (*max_element(dp + 1, dp + 1 + n)) << "\n";
}

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