Submission #688467

#	Time	Username	Problem	Language	Result	Execution time	Memory
688467		luka1234	Divide and conquer (IZhO14_divide)	C++14	100 / 100	133 ms	7580 KiB

divide

#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
using namespace std;
ll t[400001];
ll n;
ll prefg[100001];
ll prefe[100001];
ll a[100001];
void update(ll v,ll tl,ll tr,ll pos,ll x){
	if(tl==tr){
		t[v]=x;
		return;
	}
	else{
		ll m=(tl+tr)/2;
		if(pos<=m){
			update(2*v,tl,m,pos,x);
		}
		else{
			update(2*v+1,m+1,tr,pos,x);
		}
		t[v]=max(t[2*v],t[2*v+1]);
	}
}
ll get(ll v,ll tl,ll tr,ll x){
	if(tl==tr){
		return tl;
	}
	ll f1=t[2*v];
	ll f2=t[2*v+1];
	ll m=(tl+tr)/2;
	ll pas=0;
	if(f2>=x){
		pas=get(2*v+1,m+1,tr,x);
	}
	else{
		if(f1>=x){
			pas=get(2*v,tl,m,x);
		}
		else{
			pas=-1;;
		}
	}
	return pas;
}
int main(){
    cin>>n;
    for(ll k=1;k<=n;k++){
    	ll x,y,z;
    	cin>>x>>y>>z;
    	a[k]=x;
    	prefe[k]=prefe[k-1]+z;
    	prefg[k]=prefg[k-1]+y;
    	ll f=prefe[k]-a[k];
    	update(1,1,n,k,f);
	}
	ll mx=0;
	for(ll k=1;k<=n;k++){
		ll f=prefe[k-1]-a[k];
		ll ind=get(1,1,n,f);
		if(ind>=k){
			ll gl=prefg[ind]-prefg[k-1];
			mx=max(mx,gl);
		}
	}
	cout<<mx;
    return 0;
}

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