oj.uz

Submission #775395

# Submission time Handle Problem Language Result Execution time Memory
775395 2023-07-06T10:54:13 Z VMaksimoski008 Happiness (Balkan15_HAPPINESS) C++14
100 / 100
 994 ms 372064 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) 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 1 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 1 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 19 ms 13876 KB Output is correct
9 Correct 18 ms 14012 KB Output is correct
10 Correct 17 ms 13556 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 256 ms 34236 KB Output is correct
7 Correct 269 ms 33832 KB Output is correct
8 Correct 265 ms 34380 KB Output is correct
9 Correct 388 ms 44212 KB Output is correct
10 Correct 406 ms 48148 KB Output is correct
11 Correct 120 ms 33224 KB Output is correct
12 Correct 112 ms 33260 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 19 ms 13876 KB Output is correct
9 Correct 18 ms 14012 KB Output is correct
10 Correct 17 ms 13556 KB Output is correct
11 Correct 256 ms 34236 KB Output is correct
12 Correct 269 ms 33832 KB Output is correct
13 Correct 265 ms 34380 KB Output is correct
14 Correct 388 ms 44212 KB Output is correct
15 Correct 406 ms 48148 KB Output is correct
16 Correct 120 ms 33224 KB Output is correct
17 Correct 112 ms 33260 KB Output is correct
18 Correct 669 ms 220428 KB Output is correct
19 Correct 760 ms 229212 KB Output is correct
20 Correct 994 ms 372064 KB Output is correct
21 Correct 521 ms 194220 KB Output is correct
22 Correct 147 ms 33340 KB Output is correct
23 Correct 155 ms 33324 KB Output is correct
24 Correct 652 ms 211340 KB Output is correct