#include<bits/stdc++.h>
#define ll long long
#define int long long
const int nmax = 2e5 + 5, N = 1e5;
const ll oo = 1e18 + 1, base = 311;
const int lg = 20, M = 10;
const ll mod = 998244353, mod2 = 1e9 + 5277;
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;
int n, m;
int rmq[nmax][lg + 1], a[nmax];
map<int, int> dp[nmax], g[nmax];
ll f[nmax];
int calc(int u, int j){
// if(f[u] < g[u][j]) cout << "?";
dp[u][j] += f[u] - g[u][j];
g[u][j] = f[u];
return dp[u][j];
}
int get(int l, int r){
int k = __lg(r - l + 1);
int x = rmq[l][k], y = rmq[r - (1 << k) + 1][k];
if(a[x] > a[y])return x;
else return y;
}
int one[nmax];
int get(int u){
return one[u] ? one[u] = get(one[u]) : u;
}
int lmao(int x, int y){
ll res = 0;
while(dp[x].size()){
pii it = *dp[x].begin();
if(it.fi <= y){
res = max(res, calc(x, it.fi));
dp[x].erase(dp[x].begin());
}
else break;
}
return res;
}
int solve(int l, int r){
if(l == r) return l;
int p = get(l, r);
if(l < p && p < r){
int x = get(solve(l, p - 1));
int y = get(solve(p + 1, r));
if(dp[x].size() > dp[y].size()) swap(x, y);
one[x] = y;
int t1 = lmao(x, a[p]);
int t2 = lmao(y, a[p]);
f[y] += t1;
// for(auto [id, w] : dp[y]) calc(y, id);
for(auto [id, w] : dp[x]){
dp[y][id] = max(calc(x, id) + t2, calc(y, id));
}
one[p] = y;
for(auto [id, w] : dp[p]){
dp[y][id] = max(calc(y, id), w + t1 + t2);
}
dp[y][a[p]] = t2 + t1;
g[y][a[p]] = f[y];
for(int j = 1; j <= a[p]; ++j) g[y][j] = f[y];
}
else{
int y;
if(l < p)y = get(solve(l, p - 1));
else y = get(solve(p + 1, r));
int t1 = lmao(y, a[p]);
one[p] = y;
for(auto [id, w] : dp[p]){
dp[y][id] = max(calc(y, id), w + t1);
}
dp[y][a[p]] = t1;
// cout <<endl<< p << "#\n";
// for(auto [id, w] : dp[y]) cout << id << ' ' << w << endl;
// for(auto [id, w] : dp[y]){
// calc(y, id);
// }
}
return p;
}
main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("code.inp", "r", stdin);
// freopen("code.out", "w", stdout);
cin >> n;
for(int i = 1; i <= n; ++i) cin >> a[i], rmq[i][0] = i;
for(int j = 1; j <= lg; ++j){
for(int i = 1; i + (1 << j) - 1 <= n; ++i){
int x = rmq[i][j - 1], y = rmq[i + (1 << (j - 1))][j - 1];
if(a[x] > a[y]) rmq[i][j] = x;
else rmq[i][j] = y;
}
}
cin >> m;
ll sum = 0;
for(int i = 1, u, v, w; i <= m; ++i){
cin >> u >> v >> w;
dp[u][v] = w;
sum += w;
}
int p = get(solve(1, n));
ll ans = 0;
for(auto [id,w] : dp[p]) ans = max(ans, calc(p, id));
cout << sum - ans;
}
/*
6#
4 30
5 25
6 37
8 39
4#
7 37
8 39
2#
8 52
7#
2 9
3 18
4 22
5 3
*/
Compilation message
constellation3.cpp:96:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
96 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
19804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
19804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
19804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
