Submission #1187853

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187853		MrAndria	Divide and conquer (IZhO14_divide)	C++20	100 / 100	135 ms	24004 KiB

divide

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
#define int long long
const int N=3e5+5;
long long n,x[N],a[N],c[N],p[N],pr[N],d[4*N+5],ans;
vector <long long> v;
map <long long,long long> mp;
void update(int v,int tl,int tr,int pos,int val){
	if(tl==tr and tl==pos){
		d[v]=max(d[v],val);
	}else{
		int tm=(tl+tr)/2;
		if(pos<=tm){
			update(2*v,tl,tm,pos,val);
		}else{
			update(2*v+1,tm+1,tr,pos,val);
		}
		d[v]=max(d[2*v],d[2*v+1]);
	}
}
int query(int v,int tl,int tr,int l,int r){
	if(l>r)return 0;
	if(tl==l and tr==r){
		return d[v];
	}else{
		int tm=(tl+tr)/2;
		return max(query(2*v,tl,tm,l,min(tm,r)),query(2*v+1,tm+1,tr,max(tm+1,l),r));
	}
}
signed main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>c[i]>>a[i];
		pr[i]=pr[i-1]+c[i];
	}
	mp[p[1]+a[1]]++;
	if(mp[p[1]+a[1]]==1){
		v.pb(p[1]+a[1]);
	}
	for(int i=2;i<=n;i++){
		p[i]=p[i-1]+x[i]-x[i-1]-a[i];
		mp[p[i]+a[i]]++;
		if(mp[p[i]+a[i]]==1){
			v.pb(p[i]+a[i]);
		}
		mp[p[i]]++;
		if(mp[p[i]]==1){
			v.pb(p[i]);
		}
		
	}
	sort(v.begin(),v.end());
	for(int i=0;i<v.size();i++){
		mp[v[i]]=i+1;
	}
	for(int i=2;i<=n;i++){
		update(1,1,3*n,mp[p[i]],i);
	}
	for(int i=1;i<=n;i++){
		
		int j=query(1,1,3*n,1,mp[p[i]+a[i]]);
		ans=max(ans,pr[j]-pr[i-1]);
		ans=max(ans,c[i]);
//		cout<<j<<endl;
	}
	cout<<ans<<endl;
	
	
}

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52