oj.uz

답안 #41279

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
41279 2018-02-15T11:02:25 Z IvanC 금 캐기 (IZhO14_divide) C++14
100 / 100
 109 ms 25144 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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