Submission #278577

#	Time	Username	Problem	Language	Result	Execution time	Memory
278577		arnold518	Happiness (Balkan15_HAPPINESS)	C++14	100 / 100	1087 ms	134580 KiB

happiness

#include "happiness.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll MAXN = 1e18;
const int MAXVAL = 8e6;

ll M;

struct Node
{
	ll val;
	int lc, rc;
	Node() : val(0), lc(-1), rc(-1) {}
};
Node nodes[MAXVAL];

int ncnt, root;
int newNode() { return ncnt++; }

void update(int node, ll tl, ll tr, ll p, ll k)
{
	nodes[node].val+=k;
	if(tl==tr) return;
	ll mid=tl+tr>>1;
	if(p<=mid)
	{
		if(nodes[node].lc==-1) nodes[node].lc=newNode();
		update(nodes[node].lc, tl, mid, p, k);
	}
	else
	{
		if(nodes[node].rc==-1) nodes[node].rc=newNode();
		update(nodes[node].rc, mid+1, tr, p, k);
	}
}

ll query(int node, ll tl, ll tr, ll l, ll r)
{
	if(r<tl || tr<l) return 0;
	if(l<=tl && tr<=r) return nodes[node].val;
	ll mid=tl+tr>>1;
	ll ret=0;
	if(nodes[node].lc!=-1) ret+=query(nodes[node].lc, tl, mid, l, r);
	if(nodes[node].rc!=-1) ret+=query(nodes[node].rc, mid+1, tr, l, r);
	return ret;
}

void push(ll x)
{
	update(root, 1, M, x, x);
}

void pop(ll x)
{
	update(root, 1, M, x, -x);
}

bool query()
{
	ll now=1;
	ll sum=query(root, 1, M, 1, M);
	while(now<sum)
	{
		ll t=query(root, 1, M, 1, now);
		if(t<now) return 0;
		now=t+1;
	}
	return 1;
}

bool init(int coinsCount, ll maxCoinSize, ll coins[])
{
	M=maxCoinSize;
	root=newNode();

	for(int i=0; i<coinsCount; i++) push(coins[i]);
	return query();
}

bool is_happy(int event, int coinsCount, ll coins[])
{
	if(event==-1) for(int i=0; i<coinsCount; i++) pop(coins[i]);
	else for(int i=0; i<coinsCount; i++) push(coins[i]);
	return query();
}

Compilation message (stderr)

happiness.cpp: In function 'void update(int, ll, ll, ll, ll)':
happiness.cpp:29:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |  ll mid=tl+tr>>1;
      |         ~~^~~
happiness.cpp: In function 'll query(int, ll, ll, ll, ll)':
happiness.cpp:46:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |  ll mid=tl+tr>>1;
      |         ~~^~~
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