Submission #641415

#	Time	Username	Problem	Language	Result	Execution time	Memory
641415		itnes	Happiness (Balkan15_HAPPINESS)	C++14	0 / 100	1 ms	212 KiB

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 ll nTree=(1LL<<40);
ll counter=0;
	struct node{
		node *left_node=nullptr,*right_node=nullptr;
		ll val=0,lazy=0;
		node(){
			++counter;
		}
	};
	node *root=new node();
	void update(node *v,ll start,ll end,ll l,ll r,ll val){
		++counter;
		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(l<=mid){
			if(v->left_node==nullptr) v->left_node=new node();
			update(v->left_node,start,mid,l,r,val);
		}
		if(r>mid){
			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==nullptr?-INFLL:v->left_node->val),(v->right_node==nullptr?-INFLL: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);}
map<ll,int> cnt;
bool init(int coinsCount,ll maxCoinSize,ll coins[]){
	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,nTree-1,-coins[i]);
	}
	return query(1,nTree-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,nTree-1,-coins[i]);
		}else{
			--cnt[coins[i]];
			if(cnt[coins[i]]==0) update(coins[i],coins[i],-coins[i]);
			update(coins[i]+1,nTree-1,coins[i]);
		}
	}
	return query(1,nTree-1)<=1;
}
//~ int main()
//~ {
	//~ ios_base::sync_with_stdio(0);
	//~ srand(time(NULL));
	//~ int n; cin>>n;
	//~ for(int i=1;i<=n;++i){
		//~ int a=rand()%(ll)(1e12)+1,b=rand()%(ll)(1e12)+1;
		//~ if(a>b) swap(a,b);
		//~ update(a,b,rand()%(ll)(1e12)+1);
		//~ cout<<counter<<"~\n";
	//~ }
//~ }

Compilation message (stderr)

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

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40