Submission #897264

#	Time	Username	Problem	Language	Result	Execution time	Memory
897264		box	Constellation 3 (JOI20_constellation3)	C++17	0 / 100	1 ms	348 KiB

constellation3

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

#ifdef LOCAL
template <class T, class... U> void bug_h(const T& t, const U&... u) { cerr << t; ((cerr << " | " << u), ...); cerr << endl; }
#define bug(...) cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: ", bug_h(__VA_ARGS__)
#else
#define cerr if (0) cerr
#define bug(...)
#endif

#define ar array
#define all(v) std::begin(v), std::end(v)
#define sz(v) int(std::size(v))
typedef long long i64;
typedef vector<int> vi;
typedef pair<int, int> pi;

int N;
vi A;

struct segt {
    int l, r; pi mx;
    segt *lc, *rc;
    segt(int l, int r) : l(l), r(r) {
        if (l == r) mx = pi(A[l], l);
        else {
            int m = (l + r) / 2;
            lc = new segt(l, m), rc = new segt(m + 1, r);
            mx = max(lc->mx, rc->mx);
        }
    }
    pi qry(int ql, int qr) {
        if (ql <= l && qr >= r) return mx;
        if (qr <= lc->r) return lc->qry(ql, qr);
        if (ql >= rc->l) return rc->qry(ql, qr);
        return max(lc->qry(ql, qr), rc->qry(ql, qr));
    }
} *tmax;

struct node {
    vector<node *> kids;
    vector<pi> items;
    node *jump[18];
    int l, r, low, hi;
};

vector<node *> who;

node *rec(node *parent, int l, int r, int upper) {
    node *v = new node();
    if (parent == NULL) parent = v;
    v->jump[0] = parent;
    for (int l = 1; l < 18; l++)
        v->jump[l] = v->jump[l - 1]->jump[l - 1];
    v->l = l;
    v->r = r;
    v->hi = upper;
    int target = tmax->qry(l, r).first;
    v->low = target + 1;
    vector<int> cuts; int p = l;
    while (p <= r) {
        auto x = tmax->qry(p, r);
        if (x.first == target) {
            cuts.push_back(x.second);
            p = x.second + 1;
        } else break;
    }
    for (int j : cuts) who[j] = v;
    if (l < cuts.at(0)) v->kids.push_back(rec(v, l, cuts[0] - 1, target));
    for (int i = 0; i < sz(cuts) - 1; i++) if (cuts[i] + 1 < cuts[i + 1])
        v->kids.push_back(rec(v, cuts[i] + 1, cuts[i + 1] - 1, target));
    if (cuts.at(sz(cuts) - 1) < r) v->kids.push_back(rec(v, cuts.back() + 1, r, target));
    return v;
}

i64 calc(node *v) {
    vector<i64> y(sz(v->kids));
    i64 tot = 0;
    for (int i = 0; i < sz(v->kids); i++) {
        y[i] = calc(v->kids[i]);
        tot += y[i];
    }
    i64 add = 0;
    for (auto [i, w] : v->items) {
        int low = 0, hi = sz(v->kids) - 1;
        while (low < hi) {
            int mid = (low + hi) / 2;
            if (i >= v->kids[mid]->l) hi = mid;
            else low = mid + 1;
        }
        int j = low;
        i64 x = w;
        if (0 <= j && j < sz(v->kids) && v->kids[j]->r >= i)
            x -= y[j];
        add = max(add, x);
    }
    return tot + add;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    A.resize(N);
    for (auto& x : A) cin >> x;
    tmax = new segt(0, N - 1);
    who.resize(N, NULL);
    node *root = rec(NULL, 0, N - 1, N);
    int K;
    cin >> K;
    i64 sum = 0;
    while (K--) {
        int i, j, w;
        cin >> i >> j >> w, i--;
        sum += w;
        node *v = who[i];
        for (int l = 17; l >= 0; l--) {
            assert(v != NULL);
            if (v->jump[l]->low <= j)
                v = v->jump[l];
        }
        assert(v != NULL);
        assert(v->low <= j && j <= v->hi);
        v->items.push_back({i, w});
    }
    cout << sum - calc(root) << '\n';
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 21
• Subtask 3: 0 / 65