#include <iostream>
#include <array>
#include <vector>
#define ll long long
using namespace std;
vector <array<ll, 2>> V[200002];
vector <ll> H[200002];
vector <ll> U;
array<ll, 2> R[200002][2];
vector <ll> adj[200002][2];
ll n, m, l, r, mid, f, s, z, mx, opt, cnt, A[200002], bl[200002][19], br[200002][19], x, y, c;
struct SegTree_MAX{
ll st[800008];
void update(ll id, ll l, ll r, ll q, ll w) {
if (l == r) {
st[id] = max(st[id], w);
return;
}
ll mid = (l+r)/2;
if (q <= mid) update(id*2, l, mid, q, w);
else update(id*2+1, mid+1, r, q, w);
st[id] = max(st[id*2], st[id*2+1]);
}
ll query(ll id, ll l, ll r, ll ql, ll qr) {
if (qr < l || r < ql) return 0;
else if (ql <= l && r <= qr) return st[id];
ll mid = (l+r)/2;
return max(query(id*2, l, mid, ql, qr), query(id*2+1, mid+1, r, ql, qr));
}
}ST;
struct SegTree_ADD{
ll st[800008], lazy[800008];
void push(ll id) {
st[id*2] += lazy[id];
lazy[id*2] += lazy[id];
st[id*2+1] += lazy[id];
lazy[id*2+1] += lazy[id];
lazy[id] = 0;
}
void update(ll id, ll l, ll r, ll ql, ll qr, ll w) {
if (qr < l || r < ql) return;
else if (ql <= l && r <= qr) {
st[id] += w;
lazy[id] += w;
return;
}
push(id);
ll mid = (l+r)/2;
update(id*2, l, mid, ql, qr, w);
update(id*2+1, mid+1, r, ql, qr, w);
}
ll query(ll id, ll l, ll r, ll q) {
if (l == r) return st[id];
push(id);
ll mid = (l+r)/2;
if (q <= mid) return query(id*2, l, mid, q);
else return query(id*2+1, mid+1, r, q);
}
}tree[2];
void dfs(ll id, ll u) {
R[u][id][0] = cnt;
for (auto v : adj[u][id]) {
dfs(id, v);
}
R[u][id][1] = cnt++;
}
int main() {
cin >> n;
A[0] = 1e18;
for (int i=1; i<=n; ++i) {
cin >> A[i];
if (A[i] > mx) {
mx = A[i];
z = i;
}
--A[i];
}
A[n+1] = 1e18;
cin >> m;
for (int i=0; i<m; ++i) {
cin >> x >> y >> c;
--y;
f += c;
V[y].push_back({x, c});
}
V[n].push_back({z, 0});
for (int i=0; i<=n+1; ++i) {
while (!U.empty() && A[U.back()] < A[i]) U.pop_back();
if (U.empty()) bl[i][0] = i;
else bl[i][0] = U.back();
U.push_back(i);
if (i != bl[i][0]) adj[bl[i][0]][0].push_back(i);
}
U.clear();
for (int i=n+1; i>=0; --i) {
while (!U.empty() && A[U.back()] < A[i]) U.pop_back();
if (U.empty()) br[i][0] = i;
else br[i][0] = U.back();
U.push_back(i);
if (i != br[i][0]) adj[br[i][0]][1].push_back(i);
}
dfs(0, 0);
cnt = 0;
dfs(1, n+1);
for (int i=1; i<=n; ++i) {
H[A[i]].push_back(i);
}
for (int i=0; i<=n; ++i) {
for (auto [x, w] : V[i]) {
s = tree[0].query(1, 0, n+1, R[x][0][1]) + tree[1].query(1, 0, n+1, R[x][1][1]) + w;
//cout << "? " << R[x][1][1] << " " << tree[1].query(1, 0, n+1, R[x][1][1]) << endl;
//cout << x << " " << i+1 << " " << s << endl;
opt = max(opt, s);
ST.update(1, 0, n+1, x, s);
}
for (auto u : H[i]) {
s = ST.query(1, 0, n+1, bl[u][0], u);
//cout << i << " " << bl[u][0] << " " << u << " " << s << endl;
tree[0].update(1, 0, n+1, R[u][0][0], R[u][0][1], s);
z = ST.query(1, 0, n+1, u, br[u][0]);
//cout << u << " " << R[u][1][0] << " " << R[u][1][1] << " " << z << endl;
//cout << i << " " << u << " " << br[u][0] << " " << z << endl;
tree[1].update(1, 0, n+1, R[u][1][0], R[u][1][1], z);
ST.update(1, 0, n+1, u, s+z);
//cout << u << " " << s << " " << z << endl;
//opt = max(opt, s+z);
}
}
cout << f-opt << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
29532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
29532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
29532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
