Submission #1175920

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175920		VMaksimoski008	Constellation 3 (JOI20_constellation3)	C++20	100 / 100	474 ms	92020 KiB

constellation3

#include <bits/stdc++.h>
#define ar array
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const ll inf = 1e18;
const int maxn = 2e5 + 5;

struct fenwick {
    int n;
    vector<ll> tree;
    void init(int _n) { n = _n + 10; tree.resize(n+50); }

    void update(int p, ll v) {
        for(p++; p<n; p+=p&-p) tree[p] += v;
    }

    ll query(int p) {
        ll ans = 0;
        for(p++; p; p-=p&-p) ans += tree[p];
        return ans;
    }
} fwt[2];

vector<int> G[maxn];
ll dp[maxn][2];
int n, m, c[maxn], L[maxn], R[maxn], T[maxn][20], in[maxn], dep[maxn], up[maxn][20], out[maxn], timer = 1;
vector<pii> S[maxn];

int mrg(int i, int j) {
    return c[i] < c[j] ? i : j;
}

int query(int l, int r) {
    int k = __lg(r - l + 1);
    return mrg(T[l][k], T[r-(1<<k)+1][k]);
}

void add(int t, int u, ll v) {
    fwt[t].update(in[u], v);
    fwt[t].update(out[u], -v);
}


ll query(int t, int u, int v) {
    return fwt[t].query(in[v]) - fwt[t].query(in[ up[u][0] ]);
}

int jmp(int u, int d) {
    for(int j=19; j>=0; j--)
        if(d & (1 << j)) u = up[u][j];
    return u;
}

void dnc(int l, int r, int prv = 0) {
    if(l > r) return ;
    int p = query(l, r);
    in[p] = timer++;
    dep[p] = dep[prv] + 1;
    up[p][0] = prv;
    if(p < prv) L[prv] = p;
    if(prv < p) R[prv] = p;
    dnc(l, p-1, p);
    dnc(p+1, r, p);
    out[p] = timer++;
}

void dfs(int u) {
    for(int v : G[u]) {
        dfs(v);
        dp[u][0] += max(dp[v][0], dp[v][1]);
    }

    ll sum = dp[u][0];
    for(auto [v, w] : S[u]) {
        int x = jmp(v, dep[v]-dep[u]-1);
        sum -= max(dp[x][0], dp[x][1]);

        ll val = query(1, x, v);
        if(x != v) {
            int x2 = jmp(v, dep[v]-dep[x]-1);
            val -= query(0, x2, v);
        }

        dp[u][1] = max(dp[u][1], sum + val + w);
        sum += max(dp[x][0], dp[x][1]);
    }

    add(0, u, max(dp[u][0], dp[u][1]));
    for(int v : G[u]) add(1, u, max(dp[v][0], dp[v][1]));
}

signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    cin >> n;
    fwt[0].init(2*n);
    fwt[1].init(2*n);
    for(int i=1; i<=n; i++) {
        cin >> c[i], c[i] = n - c[i];
        T[i][0] = i;
    }

    for(int j=1; j<20; j++)
        for(int i=1; i+(1<<j)-1<=n; i++) T[i][j] = mrg(T[i][j-1], T[i+(1<<(j-1))][j-1]);

    dnc(1, n);

    for(int j=1; j<20; j++)
        for(int i=1; i<=n; i++) up[i][j] = up[up[i][j-1]][j-1];
    for(int i=1; i<=n; i++) {
        if(L[i]) G[i].push_back(L[i]);
        if(R[i]) G[i].push_back(R[i]);
    }

    cin >> m;
    ll sum = 0;
    for(int i=1; i<=m; i++) {
        int x, y, w; cin >> x >> y >> w;
        y = n - y + 1; sum += w;

        int u = x;
        for(int j=19; j>=0; j--)
            if(c[up[u][j]] >= y) u = up[u][j];
        S[u].push_back({ x, w });
    }

    int p = query(1, n);
    dfs(p);
    cout << sum - max(dp[p][0], dp[p][1]) << '\n';
}

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