Submission #897308

#	Time	Username	Problem	Language	Result	Execution time	Memory
897308		box	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	693 ms	127848 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 FT {
    vector<i64> t;
    FT(int n) : t(n) {}
    void add(int l, int r, i64 x) {
        if (l <= r) add(l, x), add(r + 1, -x);
    }
    void add(int i, i64 x) {
        while (i < sz(t)) {
            t[i] += x;
            i |= i + 1;
        }
    }
    i64 sum(int i) {
        i64 x = 0;
        while (i >= 0) {
            x += t[i];
            i &= i + 1, i--;
        }
        return x;
    }
} *ft;

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;
    bug(l, r, v->low, v->hi);
    vector<int> cuts; int p = l;
    while (p <= r) {
        auto x = tmax->qry(p, r);
        x.second *= -1;
        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 u : v->kids) bug(u->l, u->r);
    for (auto [i, w] : v->items) {
        cerr << "ITEM " << i << ' ' << w << endl;
        int low = 0, hi = sz(v->kids) - 1;
        while (low < hi) {
            int mid = (low + hi) / 2 + 1;
            if (i >= v->kids[mid]->l) low = mid;
            else hi = mid - 1;
        }
        int j = low;
        i64 x = w;
        bug(j);
        if (0 <= j && j < sz(v->kids) && v->kids[j]->r >= i && v->kids[j]->l <= i) {
            cerr << "CAUGHT " << j << "(subtract " << y[j] << ")" << endl;
            x -= y[j];
        }
        x += ft->sum(i);
        add = max(add, x);
    }
    for (int i = 0; i < sz(v->kids); i++) {
        ft->add(v->l, v->kids[i]->l - 1, y[i]);
        ft->add(v->kids[i]->r + 1, v->r, y[i]);
    }
    bug(v->l, v->r, v->low, v->hi, tot + add);
    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 + 1);
    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});
        bug(i, j, w, v->l, v->r, v->low, v->hi);
    }
    ft = new FT(N);
    cout << sum - calc(root) << '\n';
}

Compilation message (stderr)

constellation3.cpp: In function 'i64 calc(node*)':
constellation3.cpp:109:15: warning: unused variable 'u' [-Wunused-variable]
  109 |     for (auto u : v->kids) bug(u->l, u->r);
      |               ^

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