Submission #1166370

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166370		SulA	Divide and conquer (IZhO14_divide)	C++20	17 / 100	2 ms	652 KiB

divide

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
using namespace chrono;
template<typename T> using ordered_set = tree<T, null_type, less_equal<>, rb_tree_tag, tree_order_statistics_node_update>;
#define all(a) (a).begin(), (a).end()

struct segtree {
    vector<long long> tree;
    int offset = 1;
    segtree(int n) {
        while (offset < n) offset <<= 1;
        tree.resize(offset << 1, 1e18);
    }
    void update(int i, long long x) {
        i += offset;
        tree[i] = min(tree[i], x);
        while (i >>= 1)
            tree[i] = min(tree[2*i], tree[2*i + 1]);
    }
    long long query(int v, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return tree[v];
        if (qr < l || r < ql) return 1e18;
        int mid = (l+r)/2;
        return min({
                           query(v << 1, l, mid, ql, qr),
                           query(v << 1 | 1, mid+1, r, ql, qr)
                   });
    }
    long long query(int l, int r) { return query(1, 0, offset - 1, l, r); }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n; cin >> n;
    long long sum_e = 0;
    long long gold[n], p[n], q[n];
    for (int i = 0; i < n; i++) {
        int x,g,d; cin >> x >> g >> d;
        p[i] = x - sum_e;
        sum_e += d;
        q[i] = x - sum_e;
        gold[i] = g;
    }
    map<int, vector<int>> comp;
    for (int i = 0; i < n; i++)
        comp[p[i]].push_back(i),
        comp[q[i]].push_back(i + n);
    int u = 0;
    for (auto [val, inds] : comp) {
        for (int ind : inds)
            (ind < n ? p[ind] : q[ind - n]) = u;
        u += 1;
    }
    // [l, r] is possible iff q[r] <= p[l]
    long long sum = 0, ans = 0;
    segtree s(2*n);
    for (int i = 0; i < n; i++) {
        s.update(p[i], sum);
        sum += gold[i];
        ans = max(ans, sum - s.query(q[i], 2*n - 1));
    }
    cout << ans;
}

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