Submission #41279

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
41279	2018-02-15T11:02:25 Z	IvanC	Divide and conquer (IZhO14_divide)	C++14	100 / 100	109 ms	25144 KB

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

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.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	248 KB	Output is correct
2	Correct	1 ms	356 KB	Output is correct
3	Correct	1 ms	464 KB	Output is correct
4	Correct	1 ms	484 KB	Output is correct
5	Correct	2 ms	580 KB	Output is correct
6	Correct	2 ms	588 KB	Output is correct
7	Correct	2 ms	712 KB	Output is correct
8	Correct	2 ms	712 KB	Output is correct
9	Correct	2 ms	712 KB	Output is correct
10	Correct	2 ms	716 KB	Output is correct
11	Correct	2 ms	720 KB	Output is correct
12	Correct	2 ms	724 KB	Output is correct

Subtask #2

31.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	728 KB	Output is correct
2	Correct	2 ms	732 KB	Output is correct
3	Correct	3 ms	764 KB	Output is correct
4	Correct	2 ms	784 KB	Output is correct
5	Correct	3 ms	816 KB	Output is correct
6	Correct	2 ms	844 KB	Output is correct
7	Correct	3 ms	896 KB	Output is correct
8	Correct	2 ms	916 KB	Output is correct
9	Correct	3 ms	952 KB	Output is correct
10	Correct	4 ms	1108 KB	Output is correct
11	Correct	5 ms	1496 KB	Output is correct
12	Correct	9 ms	1512 KB	Output is correct

Subtask #3

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	1512 KB	Output is correct
2	Correct	8 ms	1960 KB	Output is correct
3	Correct	9 ms	2216 KB	Output is correct
4	Correct	44 ms	5832 KB	Output is correct
5	Correct	43 ms	7200 KB	Output is correct
6	Correct	97 ms	13344 KB	Output is correct
7	Correct	86 ms	15132 KB	Output is correct
8	Correct	76 ms	17048 KB	Output is correct
9	Correct	77 ms	18800 KB	Output is correct
10	Correct	109 ms	20484 KB	Output is correct
11	Correct	100 ms	22728 KB	Output is correct
12	Correct	99 ms	25144 KB	Output is correct