Submission #887383

#	Time	Username	Problem	Language	Result	Execution time	Memory
887383		viwlesxq	Divide and conquer (IZhO14_divide)	C++17	0 / 100	0 ms	600 KiB

divide

#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll;
#define all(x) x.begin(), x.end()
#define size(x) (int)x.size()

template<class S, class T> 
bool chmin(S &a, const T &b) {
    return (a > b ? (a = b) == b : false);
}
template<class S, class T> 
bool chmax(S &a, const T &b) {
    return (a < b ? (a = b) == b : false);
}
const ll inf = 1e18;
const int mod = 1e9 + 7;

struct Segment_Tree {
    int n;
    vector<ll> t, modify;
    Segment_Tree(int n) {
        this->n = n;
        t.assign(4 * n, -inf);
        modify.assign(4 * n, 0);
    }
    
    void push(int v, int tl, int tr) {
        t[v] += modify[v] * (tr - tl + 1);
        if (tl != tr) {
            modify[2 * v] += modify[v];
            modify[2 * v + 1] += modify[v];
        }
        modify[v] = 0;
    }
    
    void upd_pos(int v, int tl, int tr, int i, ll x) {
        if (tl == tr) {
            t[v] = x;
            return;
        }
        int tm = (tl + tr) >> 1;
        if (tm >= i) {
            upd_pos(2 * v, tl, tm, i, x);
        } else {
            upd_pos(2 * v + 1, tm + 1, tr, i, x);
        }
        t[v] = max(t[2 * v], t[2 * v + 1]);
    } void upd_pos(int i, ll x) {
        upd_pos(1, 0, n - 1, i, x);
    }
    
    void upd(int v, int tl, int tr, int l, int r, ll x) {
        if (modify[v]) {
            push(v, tl, tr);
        }
        if (tl > r || tr < l) {
            return;
        }
        if (tl >= l && tr <= r) {
            modify[v] += x;
            push(v, tl, tr);
            return;
        }
        int tm = (tl + tr) >> 1;
        upd(2 * v, tl, tm, l, r, x);
        upd(2 * v + 1, tm + 1, tr, l, r, x);
        t[v] = max(t[2 * v], t[2 * v + 1]);
    } void upd(int l, int r, ll x) {
        upd(1, 0, n - 1, l, r, x);
    }
    
    ll get(int v, int tl, int tr, int l, int r) {
        if (modify[v]) {
            push(v, tl, tr);
        }
        if (tl > r || tr < l) {
            return -inf;
        }
        if (tl >= l && tr <= r) {
            return t[v];
        }
        int tm = (tl + tr) >> 1;
        return max(get(2 * v, tl, tm, l, r), get(2 * v + 1, tm + 1, tr, l, r));
    } int get(int i) {
        int lo = i, hi = n;
        while (lo + 1 < hi) {
            int mid = (lo + hi) >> 1;
            if (get(1, 0, n - 1, mid, n - 1) >= 0) {
                lo = mid;
            } else {
                hi = mid;
            }
        }
        return lo;
    }
};

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    ll x[n], g[n], d[n], pref[n];
    for (int i = 0; i < n; ++i) {
        cin >> x[i] >> g[i] >> d[i];
    }
    Segment_Tree t(n);
    ll sum = 0;
    for (int i = 0; i < n; ++i) {
        sum += d[i];
        t.upd_pos(i, sum - x[i] + x[0]);
        pref[i] = (i == 0 ? 0 : pref[i - 1]) + g[i];
    }
    auto gold = [&](int l, int r) {
        return pref[r] - (l == 0 ? 0 : pref[l - 1]);
    };
    ll res = gold(0, t.get(0));
    for (int i = 1; i < n; ++i) {
        t.upd(i, n - 1, x[i] - x[i - 1] - d[i - 1]);
        chmax(res, gold(i, t.get(i)));
    }
    cout << res;
}

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