Submission #641405

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
641405	2022-09-16T15:42:38 Z	itnes	Happiness (Balkan15_HAPPINESS)	C++14	60 / 100	1813 ms	524288 KB

happiness

#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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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	-