Submission #388188

#	Time	Username	Problem	Language	Result	Execution time	Memory
388188		ogibogi2004	Constellation 3 (JOI20_constellation3)	C++14	0 / 100	13 ms	19148 KiB

constellation3

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=2e5+6;
const ll inf=1e16;
struct star
{
	ll x,y;
	ll c; 
}s[MAXN];
ll a[MAXN];
vector<ll>g[MAXN];
ll n,m;
struct segment_tree
{
	pair<ll,ll> tree[4*MAXN];
	void build(ll l,ll r,ll idx)
	{
		if(l==r)
		{
			tree[idx]={a[l],l};
			return;
		}
		ll 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<ll,ll> query(ll l,ll r,ll idx,ll ql,ll qr)
	{
		if(l>qr||r<ql)return {-1,-1};
		if(l>=ql&&r<=qr)return tree[idx];
		ll mid=(l+r)/2;
		return max(query(l,mid,idx*2,ql,qr),query(mid+1,r,idx*2+1,ql,qr));
	}
}st;
vector<ll>stars[MAXN];
vector<ll>stars1[MAXN];
ll cnt_nodes;
ll depth[MAXN];
ll ln[MAXN],rn[MAXN],aa[MAXN],dp[MAXN][20];
vector<pair<ll,ll> >g1[MAXN];
ll maxsum[MAXN];
ll maxsum_wot[MAXN];
void cut_nodes(ll l,ll r,ll 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<ll,ll> p=st.query(1,n,1,l,r);
	vector<ll>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);
	}
	ll t=cnt_nodes;
	reverse(v.begin(),v.end());
	for(ll 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(ll 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(ll step=1;step<20;step++)
	{
		for(ll i=1;i<=n;i++)
		{
			dp[i][step]=dp[dp[i][step-1]][step-1];
		}
	}
}
void dfs1(ll 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])
	{
		ll t=xd.first;
		for(ll 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(ll i=1;i<=n;++i)
	{
		cin>>a[i];
	}
	cin>>m;
	ll sum=0,ans=0;
	for(ll 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(ll i=1;i<=cnt_nodes;i++)
	{
		for(auto xd:stars1[i])
		{
			ll x=i;
			for(ll 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(ll 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 (stderr)

constellation3.cpp: In function 'void cut_nodes(long long int, long long int, long long int)':
constellation3.cpp:69:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |  for(ll i=0;i<v.size();i++)
      |             ~^~~~~~~~~
constellation3.cpp:76:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |  for(ll i=1;i<v.size();i++)
      |             ~^~~~~~~~~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 21
• Subtask 3: 0 / 65