Submission #1132919

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132919		OI_Account	Constellation 3 (JOI20_constellation3)	C++20	35 / 100	936 ms	74692 KiB

constellation3

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

typedef long long ll;

const int N = 200'000;
const int M = 20;
const int S = 2 * N;
const ll INF = 1'000'000'000'000'000;

int n, m, a[N + 10], mx[N + 10][M + 5];
int counter, tMark, mark[N + 10];
ll seg[4 * N + 10], dp[S + 10];
ll lazyAdd[4 * N + 10], lazyMax[4 * N + 10];
vector<pair<int, ll>> vec[N + 10], res[S + 10];
ll sum;

void readInput() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    cin >> m;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        ll c;
        cin >> c;
        sum += c;
        vec[x].push_back({y, c});
    }
}

void shift(int, int, int);

ll get(int st, int en, int id = 1, int l = 1, int r = n + 1) {
    if (en <= l || r <= st)
        return -INF;
    if (st <= l && r <= en)
        return seg[id];
    shift(id, l, r);
    int mid = (l + r) >> 1;
    return max(get(st, en, id << 1, l, mid), get(st, en, id << 1 | 1, mid, r));
}

void update(int st, int en, ll val, ll mx, int id = 1, int l = 1, int r = n + 1) {
    if (en <= l || r <= st)
        return;
    if (st <= l && r <= en) {
        seg[id] += val;
        lazyAdd[id] += val;
        lazyMax[id] += val;
        seg[id] = max(seg[id], mx);
        lazyMax[id] = max(lazyMax[id], mx);
        return;
    }
    shift(id, l, r);
    int mid = (l + r) >> 1;
    update(st, en, val, mx, id << 1, l, mid);
    update(st, en, val, mx, id << 1 | 1, mid, r);
    seg[id] = max(seg[id << 1], seg[id << 1 | 1]);
}

void shift(int id, int l, int r) {
    if (!lazyAdd[id] && lazyMax[id] == -1)
        return;
    int mid = (l + r) >> 1;
    update(l, r, lazyAdd[id], lazyMax[id], id << 1, l, mid);
    update(l, r, lazyAdd[id], lazyMax[id], id << 1 | 1, mid, r);
    lazyAdd[id] = 0;
    lazyMax[id] = -1;
}

void calcMax() {
    for (int i = 1; i <= n; i++)
        mx[i][0] = i;
    for (int j = 1; j <= M; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            if (a[mx[i][j - 1]] <= a[mx[i + (1 << (j - 1))][j - 1]])
                mx[i][j] = mx[i + (1 << (j - 1))][j - 1];
            else
                mx[i][j] = mx[i][j - 1];
}

int getMax(int l, int r) {
    int lg = 31 - __builtin_clz(r - l + 1);
    return a[mx[l][lg]] <= a[mx[r - (1 << lg) + 1][lg]]? mx[r - (1 << lg) + 1][lg]: mx[l][lg];
}

void calcVec() {
    for (int i = 1; i <= n; i++)
        sort(vec[i].begin(), vec[i].end());
}

void solveOneCell(int id, int l, int r, int last) {
    for (auto [idx, val]: vec[l])
        update(idx, n + 1, 0, val);
    dp[id] = get(1, last + 1);
    //cout << l << ' ' << r << ' ' << last << ": " << dp[id] << endl;
}

void defaltSeg() {
    update(1, n + 1, -INF, 0);
}

void checkKeep(int id, int l, int r, bool keep) {
    if (keep == true)
        return;
    tMark++;
    for (int pnt = l; pnt <= r; pnt++)
        for (auto [idx, val]: vec[pnt])
            if (mark[idx] != tMark) {
                mark[idx] = tMark;
                res[id].push_back({idx, get(1, idx + 1)});
            }
    sort(res[id].begin(), res[id].end());
    defaltSeg();
}

void changeSeg(int id, int mid, int l, int r) {
    update(a[mid], n + 1, dp[l], 0);
    for (auto [idx, val]: res[l])
        update(idx, n + 1, 0, dp[r] + val);
    for (auto [idx, val]: vec[mid])
        update(idx, n + 1, 0, dp[l] + dp[r] + val);
}

int getLen(pair<int, int> p) {
    return p.second - p.first + 1;
}

int solve(int l = 1, int r = n, int last = n, bool keep = true) {
    if (r < l) 
        return 0;
    int id = ++counter;
    if (l == r) {
        solveOneCell(id, l, r, last);
        checkKeep(id, l, r, keep);
        return id;
    }
    int mid = getMax(l, r);
    pair<int, int> p[2] = {{l, mid - 1}, {mid + 1, r}};
    if (getLen(p[0]) > getLen(p[1]))
        swap(p[0], p[1]);
    int lft = solve(p[0].first, p[0].second, a[mid], false);
    int rght = solve(p[1].first, p[1].second, a[mid], true);
    changeSeg(id, mid, lft, rght);
    dp[id] = get(1, last + 1);
    checkKeep(id, l, r, keep);
    return id;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    readInput();
    calcMax();
    calcVec();
    cout << sum - dp[solve()] << flush;
    return 0;
}

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