Submission #641412

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
641412	2022-09-16T16:16:48 Z	itnes	Happiness (Balkan15_HAPPINESS)	C++14	60 / 100	1842 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<<45);
	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	0 ms	212 KB	Output is correct
2	Correct	1 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	0 ms	212 KB	Output is correct
2	Correct	1 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	8 ms	5944 KB	Output is correct
7	Correct	9 ms	6584 KB	Output is correct
8	Correct	84 ms	51376 KB	Output is correct
9	Correct	90 ms	51844 KB	Output is correct
10	Correct	79 ms	49964 KB	Output is correct

Subtask #3

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 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	1206 ms	80476 KB	Output is correct
7	Correct	1218 ms	79628 KB	Output is correct
8	Correct	1253 ms	80428 KB	Output is correct
9	Correct	1842 ms	96480 KB	Output is correct
10	Correct	1789 ms	102484 KB	Output is correct
11	Correct	771 ms	55612 KB	Output is correct
12	Correct	762 ms	55688 KB	Output is correct

Subtask #4

0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 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	8 ms	5944 KB	Output is correct
7	Correct	9 ms	6584 KB	Output is correct
8	Correct	84 ms	51376 KB	Output is correct
9	Correct	90 ms	51844 KB	Output is correct
10	Correct	79 ms	49964 KB	Output is correct
11	Correct	1206 ms	80476 KB	Output is correct
12	Correct	1218 ms	79628 KB	Output is correct
13	Correct	1253 ms	80428 KB	Output is correct
14	Correct	1842 ms	96480 KB	Output is correct
15	Correct	1789 ms	102484 KB	Output is correct
16	Correct	771 ms	55612 KB	Output is correct
17	Correct	762 ms	55688 KB	Output is correct
18	Runtime error	1368 ms	524288 KB	Execution killed with signal 9
19	Halted	0 ms	0 KB	-