Submission #916282

#	Time	Username	Problem	Language	Result	Execution time	Memory
916282		PM1	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	625 ms	45156 KiB

constellation3

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
#define ll long long
const ll mxn=2e5+5;
ll n,m,a[mxn],par[mxn],sz[mxn],rast[mxn],chap[mxn],mxr[mxn],mxl[mxn],mark[mxn],rb[mxn],lb[mxn];
ll dp[mxn],ans=0;
struct star{
	ll xx,yy,c;
}str[mxn];
vector<pair<ll,ll> >bld;
pair<ll,ll>pd[mxn];
bool cmp(star x,star y){
	if(x.yy!=y.yy)
		return x.yy<y.yy;
	return x.xx<y.xx;
}
struct segment{
	ll val[mxn*4];
	void up(ll id,ll L,ll R,ll l,ll x){
		if(L+1==R){
			val[id]=x;
			return;
		}
		ll mid=(L+R)/2;
		if(l<mid)
			up(id*2,L,mid,l,x);
		else 
			up(id*2+1,mid,R,l,x);
		val[id]=val[id*2]+val[id*2+1];
	}
	ll get(ll id,ll L,ll R,ll l,ll r){
		if(L==l && R==r)
			return val[id];
		ll mid=(L+R)/2,res=0;
		if(l<mid)
			res+=get(id*2,L,mid,l,min(r,mid));
		if(r>mid)
			res+=get(id*2+1,mid,R,max(l,mid),r);
		return res;
	}
}seg[2];
ll fndpar(ll x){
	return (par[x]==0?x:par[x]=fndpar(par[x]));
}
void dsu(ll x,ll y){
	if(x==y)return;
	ll L=min(chap[x],chap[y]),R=max(rast[x],rast[y]);
	ll l=(a[mxl[x]]<a[mxl[y]])?mxl[y]:mxl[x];
	ll r=(a[mxr[x]]>a[mxr[y]])?mxr[x]:mxr[y];
	if(sz[x]<sz[y])swap(x,y);
	sz[x]+=sz[y];
	par[y]=x;
	mxl[x]=l;
	mxr[x]=r;
	chap[x]=L;
	rast[x]=R;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(ll i=1;i<=n;i++){
		cin>>a[i];
		bld.push_back({a[i],i});
		chap[i]=rast[i]=i;
		mxr[i]=mxl[i]=i;
	}
	a[n+1]=n+1;
	a[0]=n+2;
	bld.push_back({n+1,n+1});
	chap[n+1]=rast[n+1]=n+1;
	mxr[n+1]=mxl[n+1]=n+1;
	cin>>m;
	for(ll i=1;i<=m;i++){
		cin>>str[i].xx>>str[i].yy>>str[i].c;
		ans+=str[i].c;
	}
	sort(bld.begin(),bld.end());
	sort(str+1,str+m+1,cmp);
	ll p=1;
	/////0=sc=rast ,fr=1=chap
	for(ll i=0;i<=n;i++){
		while(p<=m && str[p].yy<=bld[i].fr){
			ll x=fndpar(str[p].xx);
			ll w1=seg[0].get(1,1,n+2,str[p].xx,rast[x]+1);
			ll w2=seg[1].get(1,1,n+2,chap[x],str[p].xx+1);
			dp[p]=str[p].c+w1+w2;
			if(a[chap[x]-1]<=a[rast[x]+1])
				rb[chap[x]-1]=max(rb[chap[x]-1],dp[p]);
			else
				lb[rast[x]+1]=max(lb[rast[x]+1],dp[p]);
			p++;
		}
		ll x1=(mark[bld[i].sc+1])?fndpar(bld[i].sc+1):bld[i].sc;
		ll x2=(mark[bld[i].sc-1])?fndpar(bld[i].sc-1):bld[i].sc;
		//cout<<mxr[x1]<<" "<<rast[x1]<<" "<<chap[x2]<<" "<<mxl[x2]<<endl;
		ll z1=seg[1].get(1,1,n+2,bld[i].sc,mxr[x1]+1)+seg[0].get(1,1,n+2,mxr[x1],rast[x1]+1);
		ll z2=seg[0].get(1,1,n+2,mxl[x2],bld[i].sc+1)+seg[1].get(1,1,n+2,chap[x2],mxl[x2]+1);
		ll q1=seg[0].get(1,1,n+2,bld[i].sc,rast[x1]+1);
		ll q2=seg[1].get(1,1,n+2,chap[x2],bld[i].sc+1);
		//cout<<z2<<endl;
		pd[bld[i].sc].fr=max(z2,lb[bld[i].sc])-q2;
		pd[bld[i].sc].sc=max(z1,rb[bld[i].sc])-q1;
		seg[0].up(1,1,n+2,bld[i].sc,pd[bld[i].sc].sc);
		seg[1].up(1,1,n+2,bld[i].sc,pd[bld[i].sc].fr);
		dsu(x2,bld[i].sc);
		dsu(fndpar(bld[i].sc),x1);
		mark[bld[i].sc]=1;
		//cout<<bld[i].sc<<" "<<pd[bld[i].sc].fr<<" "<<pd[bld[i].sc].sc<<endl;
	}
	cout<<ans-seg[1].get(1,1,n+2,1,n+2);

}

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