Submission #925159

#	Time	Username	Problem	Language	Result	Execution time	Memory
925159		myst6	Happiness (Balkan15_HAPPINESS)	C++14	100 / 100	884 ms	256500 KiB

happiness

#include "happiness.h"
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
struct Node {
	ll sum;
	Node *left, *right;
	Node() : sum(0), left(nullptr), right(nullptr) {}
	void update(ll v, ll xl, ll xr, ll delta) {
		sum += delta;
		if (xl == xr) return;
		ll xm = (xl + xr) / 2;
		if (v <= xm) {
			if (!left) left = new Node();
			left->update(v, xl, xm, delta);
		} else {
			if (!right) right = new Node();
			right->update(v, xm+1, xr, delta);
		}
	}
	ll query(ll l, ll r, ll xl, ll xr) {
		if (l > r) return 0;
		if (l == xl && r == xr) {
			return sum;
		} else {
			ll xm = (xl + xr) / 2;
			ll ans = 0;
			if (left) ans += left->query(l, min(r, xm), xl, xm);
			if (right) ans += right->query(max(l, xm+1), r, xm+1, xr);
			return ans;
		}
	}
} tree;
 
const ll hi = 1'000'000'000'005LL;
 
void add(ll coin) {
	tree.update(coin, 1, hi, +coin);
}
 
void remove(ll coin) {
	tree.update(coin, 1, hi, -coin);
}
 
bool check() {
	ll curr = 1;
	while (curr < min(hi, tree.sum)) {
		ll sum = tree.query(1, curr, 1, hi);
		if (sum < curr) return false;
		curr = sum + 1;
	}
	return true;
}
 
bool init(int coinsCount, ll maxCoinSize, ll coins[]) {
	for (int i=0; i<coinsCount; i++) add(coins[i]);
	return check();
}
 
bool is_happy(int event, int coinsCount, ll coins[]) {
	for (int i=0; i<coinsCount; i++) 
		if (event == 1) add(coins[i]);
		else remove(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