#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=2e5+6;
const int inf=1e9;
struct star
{
int x,y;
int c;
}s[MAXN];
int a[MAXN];
vector<int>g[MAXN];
int n,m;
struct segment_tree
{
pair<int,int> tree[4*MAXN];
void build(int l,int r,int idx)
{
if(l==r)
{
tree[idx]={a[l],l};
return;
}
int mid=(l+r)/2;
build(l,mid,idx*2);
build(mid+1,r,idx*2+1);
tree[idx]=max(tree[idx*2+1],tree[idx*2]);
}
pair<int,int> query(int l,int r,int idx,int ql,int qr)
{
if(l>qr||r<ql)return {-1,-1};
if(l>=ql&&r<=qr)return tree[idx];
int mid=(l+r)/2;
return max(query(l,mid,idx*2,ql,qr),query(mid+1,r,idx*2+1,ql,qr));
}
}st;
vector<int>stars[MAXN];
vector<int>stars1[MAXN];
int cnt_nodes;
int depth[MAXN];
int ln[MAXN],rn[MAXN],aa[MAXN],dp[MAXN][20];
vector<pair<int,ll> >g1[MAXN];
ll maxsum[MAXN];
ll maxsum_wot[MAXN];
void cut_nodes(int l,int r,int par)
{
if(l>r)return;
//cout<<"----\n";
//cout<<l<<" "<<r<<" "<<cnt_nodes+1<<endl;
++cnt_nodes;
ln[cnt_nodes]=l;
rn[cnt_nodes]=r;
g[par].push_back(cnt_nodes);
dp[cnt_nodes][0]=par;
depth[cnt_nodes]=depth[par]+1;
pair<int,int> p=st.query(1,n,1,l,r);
vector<int>v;
aa[cnt_nodes]=p.first;
v.push_back(p.second);
for(;;)
{
if(v.back()<=l)break;
p=st.query(1,n,1,l,v.back()-1);
if(p.first!=a[v[0]])break;
v.push_back(p.second);
}
int t=cnt_nodes;
reverse(v.begin(),v.end());
for(int i=0;i<v.size();i++)
{
//cout<<v[i]<<" ";
for(auto xd:stars[v[i]])stars1[cnt_nodes].push_back(xd);
}
//cout<<endl;
if(v[0]!=l)cut_nodes(l,v[0]-1,t);
for(int i=1;i<v.size();i++)
{
if(v[i-1]+1!=v[i])cut_nodes(v[i-1]+1,v[i]-1,t);
}
if(v.back()!=r)cut_nodes(v.back()+1,r,t);
}
void precompute()
{
for(int step=1;step<20;step++)
{
for(int i=1;i<=n;i++)
{
dp[i][step]=dp[dp[i][step-1]][step-1];
}
}
}
void dfs1(int u)
{
for(auto xd:g[u])dfs1(xd);
maxsum_wot[u]=0;
maxsum[u]=-inf;
for(auto xd:g[u])
{
maxsum_wot[u]+=max(maxsum_wot[xd],maxsum[xd]);
}
//cout<<u<<endl;
for(auto xd:g1[u])
{
int t=xd.first;
for(int i=19;i>=0;--i)
{
if(depth[dp[t][i]]<=depth[u])continue;
t=dp[t][i];
}
//cout<<xd.first<<" "<<t<<endl;
maxsum[u]=max(maxsum[u],maxsum_wot[u]-max(maxsum_wot[t],maxsum[t])+xd.second+maxsum_wot[xd.first]);
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;++i)
{
cin>>a[i];
}
cin>>m;
ll sum=0,ans=0;
for(int i=1;i<=m;++i)
{
cin>>s[i].x>>s[i].y>>s[i].c;
stars[s[i].x].push_back(i);
sum+=s[i].c;
}
st.build(1,n,1);
cut_nodes(1,n,0);
precompute();
for(int i=1;i<=cnt_nodes;i++)
{
for(auto xd:stars1[i])
{
int x=i;
for(int j=19;j>=0;j--)
{
if(dp[x][j]==0)continue;
if(aa[dp[x][j]]<s[xd].y)
{
x=dp[x][j];
}
}
//cout<<"^^^ "<<x<<" "<<i<<endl;
g1[x].push_back({i,s[xd].c});
}
}
dfs1(1);
//cout<<"^^^\n";
for(int i=1;i<=cnt_nodes;i++)
{
ans=max(ans,maxsum[i]);
ans=max(ans,maxsum_wot[i]);
}
cout<<sum-ans<<endl;
return 0;
}
Compilation message
constellation3.cpp: In function 'void cut_nodes(int, int, int)':
constellation3.cpp:69:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for(int i=0;i<v.size();i++)
| ~^~~~~~~~~
constellation3.cpp:76:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for(int i=1;i<v.size();i++)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
19280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
19280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
19280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
