Submission #934225

#	Time	Username	Problem	Language	Result	Execution time	Memory
934225		beepbeepsheep	Divide and conquer (IZhO14_divide)	C++17	0 / 100	1 ms	6492 KiB

divide

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef tree<long long, null_type, less_equal<>,
        rb_tree_tag, tree_order_statistics_node_update>
        ordered_set;
        
#define ll long long
#define ii pair<ll,ll>
#define iii tuple<ll,ll,ll>

#ifndef DEBUG
#define cerr if (0) cerr
#define endl '\n'
#endif

const ll inf=1e15;
const ll maxn=2e5+5;
const ll mod=1e9+7;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll arr[maxn],brr[maxn],crr[maxn];
ll pref[maxn];
ll bpref[maxn];
struct node{
	ll s,e,m,val;
	node *l, *r;
	node(ll _s, ll _e){
		s=_s,e=_e,m=(s+e)>>1,val=0;
		if (s!=e) l=new node(s,m),r=new node(m+1,e);
	}
	void upd(ll x, ll v){
		if (s==e){
			val=v;
			return;
		}
		if (x>m) r->upd(x,v);
		else l->upd(x,v);
		val=max(l->val,r->val);
	}
	ll query(ll x, ll y){
		if (x<=s && e<=y) return val;
		if (x>m) return r->query(x,y);
		if (y<=m) return l->query(x,y);
		return max(l->query(x,y),r->query(x,y));
	}
}*root;
ll n;
ll find(ll x, ll s){
	ll l=s,r=n+1,m; //left is legal for sure
	while (l!=r-1){
		m=(l+r)>>1;
		if (root->query(m,n)>=x) l=m;
		else r=m;
	}
	return l;
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	root=new node(1,n);
	for (int i=1;i<=n;i++){
		cin>>arr[i]>>brr[i]>>crr[i];
	}
	pref[1]=crr[1];
	root->upd(1,pref[1]);
	bpref[1]=brr[1];
	for (int i=2;i<=n;i++){
		pref[i]=pref[i-1]+crr[i]-(arr[i]-arr[i-1]);
		cerr<<pref[i]<<endl;
		root->upd(i,pref[i]);
		//difference between length and cover
		bpref[i]=brr[i]+bpref[i-1]; 
	}
	ll tot=0,ans=0; //minimally more than this
	for (int i=1;i<=n;i++){
		ll res=find(tot,i);
		ans=max(bpref[res]-bpref[i-1],ans);
		tot=pref[i];
		cerr<<tot<<endl;
	}
	cout<<ans;
	return 0;
}

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