#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<ll, ll> pii;
typedef pair<ld, ld> pld;
ll n, m;
ll a[200009];
vector<pii> b[200009];
ll dp[200009];
ll tot;
ll seg[800009];
void build(ll v, ll tl, ll tr){
if(tl == tr){
seg[v] = a[tl];
return;
}
build(2*v, tl, (tl+tr)/2);
build(2*v+1, (tl+tr)/2+1, tr);
seg[v] = max(seg[2*v], seg[2*v+1]);
}
ll get(ll v, ll tl, ll tr, ll val){
if(seg[v] < val) return n;
if(tl == tr) return tl;
if(seg[2*v+1] < val)
return get(2*v, tl, (tl+tr)/2, val);
return get(2*v+1, (tl+tr)/2+1, tr, val);
}
void erase(ll v, ll tl, ll tr, ll idx){
if(tl == tr){
seg[v] = -1;
return;
}
if(idx <= (tl+tr)/2)
erase(2*v, tl, (tl+tr)/2, idx);
else
erase(2*v+1, (tl+tr)/2+1, tr, idx);
seg[v] = max(seg[2*v], seg[2*v+1]);
}
ll extra[200009];
int main() {
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
cin >> n;
for(ll i = 0; i < n; ++i)
cin >> a[i];
cin >> m;
while(m--){
ll x, y, c;
cin >> x >> y >> c;
b[x-1].pb({y, c});
tot += c;
}
build(1, 0, n-1);
deque<pii> v = {{1e9+9, n}};
for(ll i = n-1; i >= 0; --i){
erase(1, 0, n-1, i);
extra[i] = max(extra[i], extra[i+1]);
dp[i] = dp[i+1];
for(auto u : b[i]){
ll bef = get(1, 0, n-1, u.ff);
if(bef < i)
extra[bef] = max(extra[bef], extra[i]+u.ss);
ll idx = (*lower_bound(v.begin(), v.end(), mp(u.ff, 0LL))).ss;
dp[i] = max(dp[i], u.ss+dp[idx]+extra[i]-extra[idx]);
}
while(v[0].ff <= a[i])
v.pop_front();
v.push_front({a[i], i});
}
cout << tot-dp[0] << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
