Submission #582026

#	Time	Username	Problem	Language	Result	Execution time	Memory
582026		Mr_Husanboy	Divide and conquer (IZhO14_divide)	C++14	100 / 100	162 ms	25568 KiB

divide

// Muallif: Mansuraliyev Husanboy Murotali o'g'li  >> NamPS
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define ull unsigned long long 
#define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(a) a.begin(), a.end()
#define F first
#define S second
#define fp(a,i,c) for(int (a) = (i); (a) < (c); (a)++)
#define fm(a,i,c) for(int (a) = (i); (a) >= (c); (a)--)
#define vii vector<int>
#define vll vector<ll>
// 0-9 >> 48-57;    A-Z>>65-90   and   a-z>>97-122 respectively;
const ll mod=1e9+7;

ll t[400005];

void upd(ll x, ll l, ll r, ll ind, ll val){
	//if(ind<l||ind>r) return;
	if(l==r){
		t[x]=val;return;
	}
	//if(ind<l||ind>r) return;
	ll m=(l+r)/2;
	if(ind<=m) upd(x*2,l,m,ind,val); else upd(x*2+1,m+1,r,ind,val);
	t[x]=max(t[x*2],t[x*2+1]);
}

ll get(ll x, ll l, ll r, ll lx, ll rx){
	if(lx<=l&&r<=rx){
		return t[x];
	}
	if(l>rx||lx>r) return 0;
	ll m=(l+r)/2;
	return max(get(x*2,l,m,lx,rx),get(x*2+1,m+1,r,lx,rx));
}




void solve(){
	int n; cin>>n;
	vector<ll> x(n+1),g(n+1),en(n+1);
	for(int i=1;i<=n;i++){
		ll a,b,c; cin>>a>>b>>c;
		x[i]=a; g[i]=g[i-1]+b,en[i]=en[i-1]+c;
	}
	vector<ll> dif(n+1); map<ll,int>mp;
	multiset<ll> st;
	//ll mn=1e18,mx=-1e18;
	for(int i=1;i<=n;i++){
		x[i]-=x[1];
		dif[i]=en[i]-x[i];
		st.insert(dif[i]);
		//mn=min(mn,dif[i]); mx=max(mx,dif[i]);
		mp[dif[i]]=max(i,mp[dif[i]]);
	}ll ans=0;
	ll mn=1,mx=mp.size(); ll cur=1;
	map<ll,ll> indtree;
	for(auto u:mp){
		indtree[u.F]=cur;
		cur++;
	}
	for(auto u:mp){
		//cout<<"d"<<endl;
		upd(1,mn,mx,indtree[u.F],u.S);
	}
//	cout<<"a"<<endl;
	for(int i=1;i<=n;i++){
		ans=max(ans,g[get(1,mn,mx,indtree[*st.lower_bound(en[i-1]-x[i])],indtree[*--st.end()])]-g[i-1]);
	//	cout<<i<<": "<<get(1,mn,mx,indtree[*st.lower_bound(en[i-1]-x[i])],indtree[*--st.end()])<<endl;
		st.erase(st.find(dif[i]));
	//	cout<<ans<<endl;
	}
	cout<<ans;
}
 
int main(){
	ios;
//	int t; cin>>t; while(t--)
	solve();
}

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