Submission #701046

#	Time	Username	Problem	Language	Result	Execution time	Memory
701046		Kahou	Constellation 3 (JOI20_constellation3)	C++14	35 / 100	1583 ms	20928 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];
vector<pair<ll, pll>> vc;
ll adj[N][2];

void solve() {
        cin >> n;
        for (int i = 1; i <= n; i++) {
                cin >> a[i];
        }
        cin >> m;
        ll sm = 0;
        for (int i = 1; i <= m; i++) {
                ll x, y, w;
                cin >> x >> y >> w;
                vc.push_back({y, {-w, x}});
                sm += 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 (auto P: vc) {
                ll y = P.F;
                ll x = P.S.S;
                ll w = -P.S.F;
                ll tmp = dp[x][0] + dp[x][1] + w;
                ll u = par[x];
                while (a[u] < y) {
                        tmp += dp[u][u>x];
                        u = par[u];
                }
                dp[u][u<x] = max(dp[u][u<x], tmp);
        }
        cout << sm-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: 0 / 65