oj.uz

답안 #641405

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
641405 2022-09-16T15:42:38 Z itnes Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 1813 ms 524288 KB 
#include "happiness.h"
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef pair<int,int> pii;
const ll INFLL=1e18+7;
const int INF=1e9+7;
#define pb push_back
const int MAXN=1e6+7;
const ll nTree=(1LL<<41);
	struct node{
		node *left_node=nullptr,*right_node=nullptr;
		ll val=0,lazy=0;
	};
	node *root=new node();
	void update(node *v,ll start,ll end,ll l,ll r,ll val){
		if(v->lazy!=0){
			v->val+=v->lazy;
			if(start!=end){
				if(v->left_node==nullptr) v->left_node=new node();
				v->left_node->lazy+=v->lazy;
				if(v->right_node==nullptr) v->right_node=new node();
				v->right_node->lazy+=v->lazy;
			}
			v->lazy=0;
		}
		if(start>r||end<l||start>end) return;
		if(start>=l&&end<=r){
			v->val+=val;
			if(start!=end){
				if(v->left_node==nullptr) v->left_node=new node();
				v->left_node->lazy+=val;
				if(v->right_node==nullptr) v->right_node=new node();
				v->right_node->lazy+=val;
			}
			return;
		}
		ll mid=(start+end)>>1;
		if(v->left_node==nullptr) v->left_node=new node();
		update(v->left_node,start,mid,l,r,val);
		if(v->right_node==nullptr) v->right_node=new node();
		update(v->right_node,mid+1,end,l,r,val);
		v->val=max(v->left_node->val,v->right_node->val);
	}
	ll query(node *v,ll start,ll end,ll l,ll r){
		if(start>r||end<l||start>end) return -INFLL;
		if(v->lazy!=0){
			v->val+=v->lazy;
			if(start!=end){
				if(v->left_node==nullptr) v->left_node=new node();
				v->left_node->lazy+=v->lazy;
				if(v->right_node==nullptr) v->right_node=new node();
				v->right_node->lazy+=v->lazy;
			}
			v->lazy=0;
		}
		if(start>=l&&end<=r) return v->val;
		ll mid=(start+end)>>1;
		if(v->left_node==nullptr) v->left_node=new node();
		if(v->right_node==nullptr) v->right_node=new node();
		return max(query(v->left_node,start,mid,l,r),query(v->right_node,mid+1,end,l,r));
	}
	void update(ll l,ll r,ll val){update(root,0,nTree-1,l,r,val);}
	ll query(ll l,ll r){return query(root,0,nTree-1,l,r);}
ll N;
map<ll,int> cnt;
bool init(int coinsCount,ll maxCoinSize,ll coins[]){
	N=maxCoinSize;
	for(int i=0;i<coinsCount;++i){
		++cnt[coins[i]];
		if(cnt[coins[i]]==1) update(coins[i],coins[i],coins[i]);
		update(coins[i]+1,N+1,-coins[i]);
	}
	return query(1,N+1)<=1;
}
bool is_happy(int event,int coinsCount,ll coins[]){
	for(int i=0;i<coinsCount;++i){
		if(event==1){
			++cnt[coins[i]];
			if(cnt[coins[i]]==1) update(coins[i],coins[i],coins[i]);
			update(coins[i]+1,N+1,-coins[i]);
		}else{
			--cnt[coins[i]];
			if(cnt[coins[i]]==0) update(coins[i],coins[i],-coins[i]);
			update(coins[i]+1,N+1,coins[i]);
		}
	}
	return query(1,N+1)<=1;
}
//~ int main()
//~ {
	//~ ios_base::sync_with_stdio(0);
	//~ cout<<init(5,100,{4,8,1,2,16})<<"\n";
	//~ cout<<is_happy(-1,2,{2,8})<<"\n";
	//~ cout<<is_happy(1,3,{7,9,2})<<"\n";
//~ }

Compilation message

grader.cpp: In function 'int main()':
grader.cpp:16:12: warning: unused variable 'max_code' [-Wunused-variable]
   16 |  long long max_code;
      |            ^~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 10 ms 5972 KB Output is correct
7 Correct 9 ms 6524 KB Output is correct
8 Correct 91 ms 51228 KB Output is correct
9 Correct 83 ms 51660 KB Output is correct
10 Correct 77 ms 50052 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1196 ms 80104 KB Output is correct
7 Correct 1125 ms 79268 KB Output is correct
8 Correct 1171 ms 79908 KB Output is correct
9 Correct 1813 ms 95956 KB Output is correct
10 Correct 1813 ms 102204 KB Output is correct
11 Correct 773 ms 55400 KB Output is correct
12 Correct 751 ms 55320 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 10 ms 5972 KB Output is correct
7 Correct 9 ms 6524 KB Output is correct
8 Correct 91 ms 51228 KB Output is correct
9 Correct 83 ms 51660 KB Output is correct
10 Correct 77 ms 50052 KB Output is correct
11 Correct 1196 ms 80104 KB Output is correct
12 Correct 1125 ms 79268 KB Output is correct
13 Correct 1171 ms 79908 KB Output is correct
14 Correct 1813 ms 95956 KB Output is correct
15 Correct 1813 ms 102204 KB Output is correct
16 Correct 773 ms 55400 KB Output is correct
17 Correct 751 ms 55320 KB Output is correct
18 Runtime error 1430 ms 524288 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -