Submission #895175

#	Time	Username	Problem	Language	Result	Execution time	Memory
895175		amirhoseinfar1385	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	415 ms	63988 KiB

constellation3

#include<bits/stdc++.h>
using namespace std;
const long long maxn=200000+10;
struct node{
	long long x,y,w,l,r;
}allq[maxn];
vector<int>allqi[maxn];
long long all[maxn],q,n;
vector<long long>sn,si;
pair<long long,long long>val[maxn],fakeval[maxn],fa[maxn],mx[maxn],val2[maxn];
pair<vector<long long>,vector<long long>>fmx[maxn];
int kaf=(1<<18);

struct segment{
	long long seg[(1<<19)];
	void upd(int i,long long w){
		while(i!=0){
			seg[i]+=w;
			i>>=1;
		}
	}
	long long pors(int i,int l,int r,int tl,int tr){
		if(l>r||l>tr||r<tl||tl>tr){
			return 0ll;
		}
		if(l>=tl&&r<=tr){
			return seg[i];
		}
		int m=(l+r)>>1;
		long long ret=pors((i<<1),l,m,tl,tr);
		ret+=pors((i<<1)^1,m+1,r,tl,tr);
		return ret;
	}
}val2f,val2s;

bool cmpn(long long a,long long b){
	return allq[a].y<allq[b].y;
}

bool cmpi(long long a,long long b){
	if(all[a]==all[b]){
		return a<b;
	}
	return all[a]<all[b];
}

void callr()
{
	deque<pair<long long,long long>>allind;
	allind.push_back(make_pair(n+2,0));
	for(int i=1;i<=n;i++){
		for(auto x:allqi[i]){
			int p=lower_bound(allind.begin(),allind.end(),make_pair(allq[x].y,0ll))-allind.begin();
			allq[x].l=allind[p].second;
		}	
		while((int)allind.front().first<all[i]){
			if(mx[i].first==allind.front().first){
				fmx[i].first.push_back(allind.front().second);
			}
			if(mx[i].first<allind.front().first){
				mx[i].first=allind.front().first;
				fmx[i].first.clear();
				fmx[i].first.push_back(allind.front().second);
			}
			allind.pop_front();
		}
		fa[i].first=allind.front().second;
		allind.push_front(make_pair(all[i],i));
	}
	allind.clear();
	allind.push_back(make_pair(n+1,n+1));
	for(int i=n;i>=1;i--){
		for(auto x:allqi[i]){
			int p=lower_bound(allind.begin(),allind.end(),make_pair(allq[x].y,0ll))-allind.begin();
			allq[x].r=allind[p].second;
		}
		while((int)allind.front().first<all[i]){
			if(mx[i].second==allind.front().first){
				fmx[i].second.push_back(allind.front().second);
			}
			if(mx[i].second<allind.front().first){
				mx[i].second=allind.front().first;
				fmx[i].second.clear();
				fmx[i].second.push_back(allind.front().second);
			}
			allind.pop_front();
		}
		fa[i].second=allind.front().second;
		allind.push_front(make_pair(all[i],i));
	}
}
long long mainres=0;

void updn(long long ind){
	long long res=0,resa=0;
	long long maxa=-1;
	res+=val2s.pors(1,0,kaf-1,allq[ind].x,allq[ind].r-1);
	maxa=-1;
	res+=val2f.pors(1,0,kaf-1,allq[ind].l+1,allq[ind].x);
	res+=resa+allq[ind].w;
	fakeval[allq[ind].r].first=max(fakeval[allq[ind].r].first,res);
	fakeval[allq[ind].l].second=max(fakeval[allq[ind].l].second,res);
	mainres=max(mainres,res);
}

void upd(long long ind){
	val[ind]=fakeval[ind];
	long long res=0,maxa=-1;
	vector<long long>v;
	if(fa[ind].first!=ind-1){
		v=fmx[ind].first;
		if((long long)v.size()>0){
			for(auto x:v){
				res+=val[x].second;
			}
			res+=val[v.back()].first;
			val[ind].first=max(val[ind].first,res);
		}
	}
	res=0,maxa=-1;
	v.clear();
	if(fa[ind].second!=ind+1){
		v=fmx[ind].second;
		if((long long)v.size()>0){
			for(auto x:v){
				res+=val[x].first;
			}
			res+=val[v.back()].second;
			val[ind].second=max(val[ind].second,res);
		}
	}
	mainres=max(mainres,max(val[ind].first,val[ind].second));
	val2[ind].first=-val2f.pors(1,0,kaf-1,fa[ind].first+1,ind-1);
	val2[ind].first+=val[ind].first;
	val2f.upd(ind+kaf,val2[ind].first);
	val2[ind].second=-val2s.pors(1,0,kaf-1,ind+1,fa[ind].second-1);
	val2[ind].second+=val[ind].second;
	val2s.upd(ind+kaf,val2[ind].second);
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(long long i=1;i<=n;i++){
		cin>>all[i];
		si.push_back(i);
	}
	cin>>q;
	long long suma=0;
	for(long long i=1;i<=q;i++){
		sn.push_back(i);
		cin>>allq[i].x>>allq[i].y>>allq[i].w;
		allqi[allq[i].x].push_back(i);
		suma+=allq[i].w;
	}
	callr();
	sort(sn.begin(),sn.end(),cmpn);
	sort(si.begin(),si.end(),cmpi);
	long long i=0,j=0;
	while(i<(long long)sn.size()&&j<(long long)si.size()){
		if(allq[sn[i]].y<=all[si[j]]){
			updn(sn[i]);
			i++;
		}
		else{
			upd(si[j]);
			j++;
		}
	}
	while(i<(long long)sn.size()){
		updn(sn[i]);
		i++;
	}
	while(j<(long long)si.size()){
		upd(si[j]);
		j++;
	}
	long long now=(long long)si.size()-1;
	long long res=val[si[now]].second;
	while(now!=0&&all[si[now-1]]==all[si[now]]){
		now--;
		res+=val[si[now]].second;
	}
	res+=val[si[now]].first;
	mainres=max(mainres,res);
	mainres=suma-mainres;
	cout<<mainres<<"\n";
}

Compilation message (stderr)

constellation3.cpp: In function 'void updn(long long int)':
constellation3.cpp:96:12: warning: variable 'maxa' set but not used [-Wunused-but-set-variable]
   96 |  long long maxa=-1;
      |            ^~~~
constellation3.cpp: In function 'void upd(long long int)':
constellation3.cpp:108:18: warning: variable 'maxa' set but not used [-Wunused-but-set-variable]
  108 |  long long res=0,maxa=-1;
      |                  ^~~~

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