// In the name of God
// sorry M
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
const int N = 2e5 + 5, L = 3;
int n, m, A[N], H[N];
int id[N], sprc[N][L], ver, tin[N], tout[N], T;
int fen[N];
set<pair<int, pair<int, int> > > st[N];
vector<int> adj[N];
ll dp[N];
ll query(int i) {
ll res = 0;
for (i; i > 0; i -= i & -i)
res += fen[i];
return res;
}
void upd(int i, int val) {
for (i; i < N; i += i & -i)
fen[i] += val;
}
void range_upd(int l, int r, int val) {
upd(l, val);
upd(r + 1, -val);
}
void _merge(int v, int u) {
if (st[v].size() < st[u].size())
st[v].swap(st[u]);
for (auto x : st[u])
st[v].insert(x);
}
void dfs(int v, int p = 0) {
tin[v] = ++T;
int lc = 0, rc = 0;
for (auto u : adj[v]) {
dfs(u, v);
_merge(v, u);
if (lc == 0)
lc = u;
else
rc = u;
}
if (rc) {
range_upd(tin[lc], tout[lc], dp[rc]);
range_upd(tin[rc], tout[rc], dp[lc]);
}
dp[v] = dp[lc] + dp[rc];
range_upd(tin[v], tin[v], dp[v]);
while (!st[v].empty() && st[v].begin()->fi <= H[p]) {
dp[v] = max(dp[v], query(tin[st[v].begin()->se.fi]) + st[v].begin()->se.se);
//cout << "rem " << v << ' ' << st[v].begin()->se.fi << ' ' << query(tin[st[v].begin()->se.fi]) << endl;
st[v].erase(st[v].begin());
}
tout[v] = ++T;
//cout << v << ' ' << dp[v] << endl;
}
int build(int l, int r) {
if (r < l)
return -1;
int lg = __lg(r - l + 1);
int v = sprc[l][lg];
if (A[v] < A[sprc[r - (1 << lg) + 1][lg]])
v = sprc[r - (1 << lg) + 1][lg];
id[v] = ++ver;
int u = ver;
H[u] = A[v];
int lc = build(l, v - 1);
int rc = build(v + 1, r);
if (lc > -1)
adj[u].pb(lc);
if (rc > -1)
adj[u].pb(rc);
return u;
}
void solve() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> A[i];
for (int i = n; i >= 1; i--) {
sprc[i][0] = i;
for (int l = 1; l < L; l++) {
sprc[i][l] = sprc[i][l - 1];
if (i + (1 << (l - 1)) <= n && A[sprc[i][l]] < A[sprc[i + (1 << (l - 1))][l - 1]])
sprc[i][l] = sprc[i + (1 << (l - 1))][l - 1];
}
}
build(1, n);
ll sum = 0;
cin >> m;
for (int i = 0; i < m; i++) {
int x, y, c; cin >> x >> y >> c;
st[id[x]].insert(mp(y, mp(id[x], c)));
sum += c;
}
H[0] = 1e9 + 10;
dfs(1);
//cout << dp[1] << endl;
cout << sum - dp[1];
}
int32_t main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
solve();
return 0;
}
Compilation message
constellation3.cpp: In function 'll query(int)':
constellation3.cpp:20:10: warning: statement has no effect [-Wunused-value]
20 | for (i; i > 0; i -= i & -i)
| ^
constellation3.cpp: In function 'void upd(int, int)':
constellation3.cpp:25:10: warning: statement has no effect [-Wunused-value]
25 | for (i; i < N; i += i & -i)
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
14420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
14420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
14420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
