Submission #343957

#	Time	Username	Problem	Language	Result	Execution time	Memory
343957		ogibogi2004	Happiness (Balkan15_HAPPINESS)	C++14	100 / 100	1599 ms	244588 KiB

happiness

#include "happiness.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXM=1e7;
const ll INF=2e17;
const ll MAXN=2e12;
struct node
{
	ll val;
	ll pl,pr;
	node()
	{
		val=0;pl=-1;pr=-1;
	}
};
node tree[MAXM];
ll sz=1;
void update(ll idx,ll l,ll r,ll q,ll val)
{
	if(l>q||r<q)return;
	if(l==r)
	{
		tree[idx].val+=val;
		return;
	}
	ll mid=(l+r)/2;
	if(mid<q)
	{
		if(tree[idx].pr==-1)
		{
			tree[idx].pr=++sz;
		}
		update(tree[idx].pr,mid+1,r,q,val);
	}
	else
	{
		if(tree[idx].pl==-1)
		{
			tree[idx].pl=++sz;
		}
		update(tree[idx].pl,l,mid,q,val);
	}
	tree[idx].val=0;
	if(tree[idx].pl!=-1)tree[idx].val+=tree[tree[idx].pl].val;
	if(tree[idx].pr!=-1)tree[idx].val+=tree[tree[idx].pr].val;
}
ll query(ll idx,ll l,ll r,ll ql,ll qr)
{
	if(l>qr||r<ql)return 0;
	if(l>=ql&&r<=qr)
	{
		return tree[idx].val;
	}
	ll mid=(l+r)/2;
	ll ret=0;
	if(tree[idx].pl!=-1)
	{
		ret+=query(tree[idx].pl,l,mid,ql,qr);
	}
	if(tree[idx].pr!=-1)
	{
		ret+=query(tree[idx].pr,mid+1,r,ql,qr);
	}
	return ret;
}
bool check()
{
	ll csum=1;
	while(csum<tree[1].val)
	{
		ll t=query(1,1,MAXN,1,csum);
		if(t<csum)return 0;
		csum=t+1;
	}
	return 1;
}
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
	for(ll i=0;i<coinsCount;i++)
	{
		update(1,1,MAXN,coins[i],coins[i]);
	}
	return check();
}
bool is_happy(int event, int coinsCount, long long coins[]) {
	
	if(event==1)
	{
		for(ll i=0;i<coinsCount;i++)
		{
			update(1,1,MAXN,coins[i],coins[i]);
		}
	}
	else
	{
		for(ll i=0;i<coinsCount;i++)
		{
			update(1,1,MAXN,coins[i],-coins[i]);
		}
	}
	return check();
}

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: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40