oj.uz

Submission #775404

# Submission time Handle Problem Language Result Execution time Memory
775404 2023-07-06T11:05:47 Z VMaksimoski008 Happiness (Balkan15_HAPPINESS) C++14
100 / 100
 995 ms 372132 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) {
		this->sum += val;
		if(l == r || l > pos || r < pos) return ;

		auto 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(ll tl, ll tr) {
		if(l > tr || tl > r) return 0;
		if(tl <= l && r <= tr) 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 304 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 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 304 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 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 3 ms 1876 KB Output is correct
8 Correct 19 ms 13860 KB Output is correct
9 Correct 21 ms 13984 KB Output is correct
10 Correct 17 ms 13524 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 304 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 263 ms 34352 KB Output is correct
7 Correct 254 ms 33872 KB Output is correct
8 Correct 285 ms 34328 KB Output is correct
9 Correct 509 ms 44168 KB Output is correct
10 Correct 447 ms 48172 KB Output is correct
11 Correct 127 ms 33280 KB Output is correct
12 Correct 123 ms 33244 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 304 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 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 3 ms 1876 KB Output is correct
8 Correct 19 ms 13860 KB Output is correct
9 Correct 21 ms 13984 KB Output is correct
10 Correct 17 ms 13524 KB Output is correct
11 Correct 263 ms 34352 KB Output is correct
12 Correct 254 ms 33872 KB Output is correct
13 Correct 285 ms 34328 KB Output is correct
14 Correct 509 ms 44168 KB Output is correct
15 Correct 447 ms 48172 KB Output is correct
16 Correct 127 ms 33280 KB Output is correct
17 Correct 123 ms 33244 KB Output is correct
18 Correct 694 ms 220468 KB Output is correct
19 Correct 710 ms 229124 KB Output is correct
20 Correct 995 ms 372132 KB Output is correct
21 Correct 569 ms 194144 KB Output is correct
22 Correct 157 ms 33416 KB Output is correct
23 Correct 164 ms 33252 KB Output is correct
24 Correct 678 ms 211360 KB Output is correct