답안 #775387

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
775387	2023-07-06T10:44:42 Z	VMaksimoski008	Happiness (Balkan15_HAPPINESS)	C++17	40 / 100	451 ms	524288 KB

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, 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

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.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	260 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct

Subtask #2

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	260 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Runtime error	362 ms	524288 KB	Execution killed with signal 9
7	Halted	0 ms	0 KB	-

Subtask #3

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	260 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	250 ms	34304 KB	Output is correct
7	Correct	261 ms	33872 KB	Output is correct
8	Correct	292 ms	34296 KB	Output is correct
9	Correct	451 ms	44104 KB	Output is correct
10	Correct	420 ms	48188 KB	Output is correct
11	Correct	118 ms	33248 KB	Output is correct
12	Correct	115 ms	33256 KB	Output is correct

Subtask #4

0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	260 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Runtime error	362 ms	524288 KB	Execution killed with signal 9
7	Halted	0 ms	0 KB	-