Submission #775364

#	Time	Username	Problem	Language	Result	Execution time	Memory
775364		VMaksimoski008	Happiness (Balkan15_HAPPINESS)	C++14	10 / 100	296 ms	37372 KiB

happiness

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

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

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

	void update(int pos, int val) {
		sum += val;
		if(l == r) return;

		auto tm = (l + r) / 2;
		if(pos <= tm) {
			if(lc == nullptr) lc = new Node(l, tm);
			lc->update(pos, val);
		} else {
			if(rc == nullptr) rc = new Node(tm+1, r);
			rc->update(pos, val);
		}
	}

	ll query(int tl, int tr) {
		if(tl > r || l > tr) return 0;
		if(r <= tr && l >= tl) return this->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++) {
		if(event == -1) root->update(coins[i], 0 - coins[i]);
		else root->update(coins[i], coins[i]);
	}
	return check();
}

Compilation message (stderr)

happiness.cpp: In constructor 'Node::Node(ll, ll)':
happiness.cpp:7:8: warning: 'Node::r' will be initialized after [-Wreorder]
    7 |  ll l, r;
      |        ^
happiness.cpp:6:8: warning:   'Node* Node::lc' [-Wreorder]
    6 |  Node *lc, *rc;
      |        ^~
happiness.cpp:9:2: warning:   when initialized here [-Wreorder]
    9 |  Node(ll l, ll r) : l(l), r(r), lc(nullptr), rc(nullptr) {}
      |  ^~~~
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: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40