#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;
const ll maxn=200005;
pll sp[20][maxn];
vector <ll> A[maxn];
vector <pll> Q[maxn];
ll n, m, root, sum, dp[maxn], bit[maxn];
ll Time, tin[maxn], tout[maxn], jump[20][maxn];
pll query(ll l, ll r)
{
ll j=__lg(r-l+1);
return max(sp[j][l], sp[j][r-(1<<j)+1]);
}
void getedge(ll l, ll r, ll rt)
{
if (l>r) return;
ll p=query(l, r).se;
if (rt) A[rt].pb(p);
else root=p;
getedge(l, p-1, p), getedge(p+1, r, p);
}
void dfs(ll u)
{
tin[u]=++Time;
for (ll i=1; i<20; i++)
jump[i][u]=jump[i-1][jump[i-1][u]];
for (ll v:A[u])
jump[0][v]=u, dfs(v);
tout[u]=Time;
}
void update(ll l, ll r, ll val)
{
for (; l<=n; l+=l&(-l)) bit[l]+=val;
for (++r; r<=n; r+=r&(-r)) bit[r]-=val;
}
ll query(ll i)
{
ll ans=0;
for (; i; i-=i&(-i)) ans+=bit[i];
return ans;
}
void dfs2(ll u)
{
ll s=0;
for (ll v:A[u]) dfs2(v), s+=v, dp[u]+=dp[v];
for (ll v:A[u]) if (v!=s)
update(tin[v], tout[v], dp[s-v]);
for (auto [x, c]:Q[u])
{
c+=query(tin[x]);
for (ll v:A[x]) c+=dp[v];
dp[u]=max(dp[u], c);
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
cin >> n;
for (ll i=1; i<=n; i++)
cin >> sp[0][i].fi, sp[0][i].se=i;
for (ll i=1; i<20; i++)
for (ll j=1; j+(1<<i)<=n+1; j++)
sp[i][j]=max(sp[i-1][j], sp[i-1][j+(1<<i-1)]);
getedge(1, n, 0), dfs(root); cin >> m;
for (ll i=1; i<=m; i++)
{
ll x, y, c, p; cin >> x >> y >> c; p=x, sum+=c;
for (ll j=19; j>=0; j--)
if (jump[j][p] && sp[0][jump[j][p]].fi<y)
p=jump[j][p];
Q[p].pb({x, c});
}
dfs2(root);
cout << sum-dp[root];
}
Compilation message
constellation3.cpp: In function 'int main()':
constellation3.cpp:81:53: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
81 | sp[i][j]=max(sp[i-1][j], sp[i-1][j+(1<<i-1)]);
| ~^~
constellation3.cpp:74:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
74 | freopen("input.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
constellation3.cpp:75:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
75 | freopen("output.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
43608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
43608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
43608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
