oj.uz

Submission #775396

# Submission time Handle Problem Language Result Execution time Memory
775396 2023-07-06T10:55:27 Z VMaksimoski008 Happiness (Balkan15_HAPPINESS) C++14
100 / 100
 983 ms 372096 KB 
#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 || l > pos || r < pos) 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

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 2 ms 1748 KB Output is correct
7 Correct 2 ms 1876 KB Output is correct
8 Correct 18 ms 13852 KB Output is correct
9 Correct 19 ms 14004 KB Output is correct
10 Correct 20 ms 13564 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 266 ms 34260 KB Output is correct
7 Correct 275 ms 33932 KB Output is correct
8 Correct 268 ms 34332 KB Output is correct
9 Correct 378 ms 44108 KB Output is correct
10 Correct 412 ms 48172 KB Output is correct
11 Correct 116 ms 33268 KB Output is correct
12 Correct 116 ms 33280 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 2 ms 1748 KB Output is correct
7 Correct 2 ms 1876 KB Output is correct
8 Correct 18 ms 13852 KB Output is correct
9 Correct 19 ms 14004 KB Output is correct
10 Correct 20 ms 13564 KB Output is correct
11 Correct 266 ms 34260 KB Output is correct
12 Correct 275 ms 33932 KB Output is correct
13 Correct 268 ms 34332 KB Output is correct
14 Correct 378 ms 44108 KB Output is correct
15 Correct 412 ms 48172 KB Output is correct
16 Correct 116 ms 33268 KB Output is correct
17 Correct 116 ms 33280 KB Output is correct
18 Correct 668 ms 220420 KB Output is correct
19 Correct 704 ms 229136 KB Output is correct
20 Correct 983 ms 372096 KB Output is correct
21 Correct 513 ms 194212 KB Output is correct
22 Correct 147 ms 33340 KB Output is correct
23 Correct 149 ms 33308 KB Output is correct
24 Correct 636 ms 211472 KB Output is correct