Submission #775395

#	Time	Username	Problem	Language	Result	Execution time	Memory
775395		VMaksimoski008	Happiness (Balkan15_HAPPINESS)	C++14	100 / 100	994 ms	372064 KiB

happiness

#include "happiness.h"
using ll = long long;

struct Node {
	ll sum = 0, l, r;
	Node *lc, *rc;

	Node(ll l, ll r) : l(l), r(r), lc(nullptr), rc(nullptr) {}

	void update(ll pos, ll val) {
		sum += val;
		if(l == r) return ;
		ll tm = (l + r) / 2;
		if(pos <= tm) {
			if(!lc) lc = new Node(l, tm);
			lc->update(pos, val);
		} else {
			if(!rc) rc = new Node(tm+1, r);
			rc->update(pos, val);
		}
	}

	ll query(long long tl, long long tr) {
		if(tl > r || l > tr) return 0;
		if(r <= tr && l >= tl) return sum;

		ll res = 0;

		if(lc) res += lc->query(tl, tr);
		if(rc) res += rc->query(tl, tr);
		return res;
	}
};

Node *root;

bool check() {
	ll curr = 1;
	ll sum = root->sum;
	while(sum > curr) {
		ll res = root->query(1, curr);
		if(res < curr) return false;
		curr = res + 1;
	}
	return true;
}

bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
	root = new Node(1, maxCoinSize);
	for (int i=0; i<coinsCount; i++) 
		root->update(coins[i], coins[i]);
	return check();
}

bool is_happy(int event, int coinsCount, long long coins[]) {
	for (int i=0; i<coinsCount; i++)
		root->update(coins[i], coins[i] * event);
	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