Submission #238479

#	Time	Username	Problem	Language	Result	Execution time	Memory
238479		kshitij_sodani	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	327 ms	48724 KiB

constellation3

#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
llo n,m;
//#define endl '\n'
llo it[200001];
llo aa,bb,cc;
llo tree[800001];
llo build(llo no,llo l,llo r){
	if(l==r){
		tree[no]=it[l];
	}
	else{
		llo mid=(l+r)/2;
		build(no*2+1,l,mid);
		build(no*2+2,mid+1,r);
		tree[no]=max(tree[no*2+1],tree[no*2+2]);
	}
}
llo query(llo no,llo l,llo r,llo aa,llo bb,llo x){
	if(r<aa or l>bb or aa>bb){
		return n;
	}
	if(tree[no]<x){
		return n;
	}
	if(l==r){
		return l;
	}
	llo mid=(l+r)/2;
	llo xx=query(no*2+1,l,mid,aa,bb,x);
	if(xx<n){
		return xx;
	}
	return query(no*2+2,mid+1,r,aa,bb,x);
}
llo query2(llo no,llo l,llo r,llo aa,llo bb,llo x){
	if(r<aa or l>bb or aa>bb){
		return -1;
	}
	if(tree[no]<x){
		return -1;
	}
	if(l==r){
		return l;
	}
	llo mid=(l+r)/2;
	llo xx=query2(no*2+2,mid+1,r,aa,bb,x);
	if(xx>-1){
		return xx;
	}
	return query2(no*2+1,l,mid,aa,bb,x);
}
vector<llo> adj[200001];
vector<pair<pair<llo,llo>,pair<llo,llo>>> dd;
llo dp[200001];
llo vis[200001];
llo tree2[200001];
void u(llo i,llo j){
	while(i<=200000){
		tree2[i]+=j;
		i+=(i&(-i));
	}
}
llo ss(llo i){
	llo tot=0;
	while(i>0){
		tot+=tree2[i];
		i-=(i&-i);
	}
	return tot;
}
llo dfs(llo no,llo par=-1){
	dp[no]=0;
	vis[no]=1;
	for(auto j:adj[no]){
		dfs(j,no);
		dp[no]+=dp[j];
	}

	for(auto j:adj[no]){
		u(dd[j].a.b+2,dp[j]);
		u(dd[no].a.b+2,-dp[j]);
//		cout<<dd[j].a.b+2<<" "<<dd[no].a.b+1<<endl;
		u(dd[no].a.a+1,dp[j]);
		u(dd[j].a.a+1,-dp[j]);
//		cout<<dd[no].a.a+1<<" "<<dd[j].a.a<<endl;
	}
	dp[no]=max(dp[no],ss(dd[no].b.a+1)+dd[no].b.b);
//	cout<<dd[no].b.a+1<<":::"<<ss(dd[no].b.a+1)<<endl;

//	cout<<no<<","<<dp[no]<<endl;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	llo su2=0;
	for(llo i=0;i<n;i++){
		cin>>it[i];
	}
	cin>>m;
	build(0,0,n-1);
	
	for(llo i=0;i<m;i++){
		cin>>aa>>bb>>cc;
		su2+=cc;
		llo ind=query2(0,0,n-1,0,aa-2,bb);
		llo ind2=query(0,0,n-1,aa,n-1,bb);
	//	cout<<ind<<"<"<<ind2<<endl;
		dd.pb({{ind+1,-(ind2-1)},{aa-1,cc}});
	}
	sort(dd.begin(),dd.end());
	for(llo i=0;i<m;i++){
		dd[i].a.b=-dd[i].a.b;
	}
/*	for(auto j:dd){
		cout<<j.a.a<<","<<j.a.b<<","<<j.b.a<<","<<j.b.b<<endl;
	}*/
	stack<pair<pair<llo,llo>,llo>> ac; 
	for(llo i=0;i<m;i++){
		pair<pair<llo,llo>,pair<llo,llo>> kk=dd[i];
		while(ac.size()){
			if(ac.top().a.b<kk.a.b){
				ac.pop();
			}			
			else{
				adj[ac.top().b].pb(i);
			//	cout<<ac.top().b<<":"<<i<<endl;
				break;
			}
		}
		ac.push({kk.a,i});
	}
	llo ans=0;
	for(llo i=0;i<m;i++){
		if(vis[i]==0){
			dfs(i);
			ans+=dp[i];
		}
	}

	cout<<su2-ans<<endl;
	return 0;
}

Compilation message (stderr)

constellation3.cpp: In function 'llo build(llo, llo, llo)':
constellation3.cpp:24:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
constellation3.cpp: In function 'llo dfs(llo, llo)':
constellation3.cpp:98:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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