제출 #701062

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
701062		Kahou	별자리 3 (JOI20_constellation3)	C++14	100 / 100	165 ms	24456 KiB

constellation3

/* In the name of God, aka Allah */
// Believe me - Takeshi Abo
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
#define mk make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = 2e5 + 50;
ll n, m, a[N], pr[N], dp[N][2], par[N], nxt[N], sm[N];
vector<pair<ll, pll>> vc;
ll adj[N][2];

int getnxt(int u, int y) {
        if (a[u] >= y) return u;
        ll v = getnxt(nxt[u], y);
        sm[u] = sm[u] + sm[nxt[u]] - dp[nxt[u]][nxt[u]<u]*(v != nxt[u]);
        nxt[u] = v;
        return v;
}

void solve() {
        cin >> n;
        for (int i = 1; i <= n; i++) {
                cin >> a[i];
        }
        cin >> m;
        ll sum = 0;
        for (int i = 1; i <= m; i++) {
                ll x, y, w;
                cin >> x >> y >> w;
                vc.push_back({y, {-w, x}});
                sum += w;
        }
        for (int i = 1; i <= n; i++) {
                vc.push_back({a[i], {0, i}});
        }
        sort(vc.begin(), vc.end());
        a[0] = a[n+1] = N;
        for (int i = 1; i <= n+1; i++) {
                pr[i] = i-1;
                while (pr[i] > 0 && a[pr[i]] <= a[i]) {
                        if (a[pr[pr[i]]] > a[i]) {
                                par[pr[i]] = i;
                                adj[i][0] = pr[i];
                        }
                        else {
                                par[pr[i]] = pr[pr[i]];
                                adj[pr[pr[i]]][1] = pr[i];
                        }
                        pr[i] = pr[pr[i]];
                }
        }
        for (int u = 1; u <= n; u++) {
                nxt[u] = par[u];
        }
        for (auto P: vc) {
                ll y = P.F;
                ll u = P.S.S;
                ll w = -P.S.F;
                if (!w) {
                        sm[u] = dp[u][0] + dp[u][1];
                        dp[par[u]][par[u]<u] = sm[u];
                        continue;
                }
                ll v = getnxt(u, y);
                dp[v][v<u] = max(dp[v][v<u], sm[u]+w);
        }
        cout << sum-dp[0][1] << endl;
}
int main() {
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        solve();
        return 0;
}

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