제출 #895097

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
895097		amirhoseinfar1385	별자리 3 (JOI20_constellation3)	C++17	0 / 100	1 ms	6492 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];
long long all[maxn],q,n;
vector<long long>sn,si;
pair<long long,long long>val[maxn],fakeval[maxn];
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()
{
	for(long long i=1;i<=q;i++){
		long long l=allq[i].x,r=allq[i].x;
		while(l!=0&&all[l]<allq[i].y){
			l--;
		}
		while(r!=n+1&&all[r]<allq[i].y){
			r++;
		}
		allq[i].l=l;
		allq[i].r=r;
	}
}
long long mainres=0;

void updn(long long ind){
	long long res=0,resa=0;
	long long maxa=-1;
	for(long long i=allq[ind].x;i<allq[ind].r;i++){
		if(all[i]>=maxa){
			res+=val[i].second;
			maxa=all[i];
		}
	}
	maxa=-1;
	for(long long i=allq[ind].x;i>allq[ind].l;i--){
		if(all[i]>=maxa){
			res+=val[i].first;
			maxa=all[i];
		}
	}
	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);
//	cout<<ind<<" "<<allq[ind].l<<" "<<allq[ind].r<<" "<<res<<"\n";
	mainres=max(mainres,res);
}

void upd(long long ind){
	val[ind]=fakeval[ind];
//	cout<<ind<<" "<<val[ind].first<<" "<<val[ind].second<<"\n";
	long long res=0,maxa=-1;
	vector<long long>v;
	long long i=ind-1;
	while(i!=0&&all[i]<all[ind]){
		if(all[i]>maxa){
			v.clear();
			maxa=all[i];
			v.push_back(i);
		}
		else if(all[i]==maxa){
			v.push_back(i);
		}
		i--;
	}
	if((long long)v.size()>0){
		for(auto x:v){
			res+=val[x].first;
		}
		res+=val[v.back()].second;
		val[ind].first=max(val[ind].first,res);
	}
	res=0,maxa=-1;
	v.clear();
	i=ind+1;


	while(i!=n+1&&all[i]<all[ind]){
		if(all[i]>maxa){
			v.clear();
			maxa=all[i];
			v.push_back(i);
		}
		else if(all[i]==maxa){
			v.push_back(i);
		}
		i++;
	}
	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));
}

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;
		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";
}

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