Submission #41279

#	Time	Username	Problem	Language	Result	Execution time	Memory
41279		IvanC	Divide and conquer (IZhO14_divide)	C++14	100 / 100	109 ms	25144 KiB

divide

#include <bits/stdc++.h>
using namespace std;
random_device rd;
knuth_b gen(rd());
typedef long long ll;
typedef struct node* pnode;
struct node{
	pnode l,r;
	ll key,prior,puro,minimo;
	node(ll _key,ll _puro) : l(NULL),r(NULL),key(_key),prior(gen()),puro(_puro),minimo(_puro){}
};
inline void upd(pnode t){
	if(!t) return;
	t->minimo = t->puro;
	if(t->l) t->minimo = min(t->minimo,t->l->minimo);
	if(t->r) t->minimo = min(t->minimo,t->r->minimo);
}
void split(pnode t,ll key,pnode &l,pnode &r){
	if(t == NULL){
		l = r = NULL;
	}
	else if(key < t->key){
		split(t->l,key,l,t->l);
		r = t;
	}
	else{
		split(t->r,key,t->r,r);
		l = t;
	}
	upd(t);
}
void merge(pnode &t,pnode l,pnode r){
	if(l == NULL){
		t = r;
	}
	else if(r == NULL){
		t = l;
	}
	else if(l->prior > r->prior){
		merge(l->r,l->r,r);
		t = l;
	}
	else{
		merge(r->l,l,r->l);
		t = r;
	}
	upd(t);
}
void insert(pnode &t,ll key,ll puro){
	pnode L,R;
	pnode aux = new node(key,puro);
	split(t,key-1,L,R);
	merge(t,L,aux);
	merge(t,t,R);
}
ll query(pnode &t,ll val){
	pnode L,R;
	split(t,val-1,L,R);
	ll resp = R->minimo;
	merge(t,L,R);
	return resp;
}
int main(){
	ll N,ans = 0,somad = 0,somag = 0;
	pnode raiz = NULL;
	scanf("%lld",&N);
	for(int i = 1;i<=N;i++){
		ll x,g,d;
		scanf("%lld %lld %lld",&x,&g,&d);
		insert(raiz, x - somad, somag );
		somad += d;
		somag += g;
		ll cand = somag - query(raiz, x - somad );
		ans = max(ans,cand);
	}
	printf("%lld\n",ans);
	return 0;
}

Compilation message (stderr)

divide.cpp: In function 'int main()':
divide.cpp:66:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&N);
                  ^
divide.cpp:69:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld %lld",&x,&g,&d);
                                   ^

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