제출 #775377

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
775377		VMaksimoski008	Happiness (Balkan15_HAPPINESS)	C++14	40 / 100	402 ms	524288 KiB

happiness

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

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

	Node(ll tl, ll tr) : sum(0), l(tl), r(tr), lc(nullptr), rc(nullptr) {}

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

	ll query(ll tl, ll 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, ll maxCoinSize, ll 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, ll coins[]) {
	for(int i=0; i<coinsCount; i++)
		root->update(coins[i], coins[i] * event);
	return check();
}

컴파일 시 표준 에러 (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: 0 / 20
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40