oj.uz

Submission #775392

# Submission time Handle Problem Language Result Execution time Memory
775392 2023-07-06T10:52:07 Z VMaksimoski008 Happiness (Balkan15_HAPPINESS) C++17
100 / 100
 1081 ms 380112 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) {
			ll tm = (l + r) / 2;
			if(pos > tm) {
				if(!rc) rc = new Node(tm+1, r);
				rc->update(pos, val);
			} else {
				if(!lc) lc = new Node(l, tm);
				lc->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 0 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 0 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 27 ms 14104 KB Output is correct
9 Correct 20 ms 14128 KB Output is correct
10 Correct 24 ms 13736 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 0 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 257 ms 34268 KB Output is correct
7 Correct 272 ms 33996 KB Output is correct
8 Correct 261 ms 34276 KB Output is correct
9 Correct 378 ms 44136 KB Output is correct
10 Correct 429 ms 48172 KB Output is correct
11 Correct 135 ms 33228 KB Output is correct
12 Correct 112 ms 33220 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 0 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 27 ms 14104 KB Output is correct
9 Correct 20 ms 14128 KB Output is correct
10 Correct 24 ms 13736 KB Output is correct
11 Correct 257 ms 34268 KB Output is correct
12 Correct 272 ms 33996 KB Output is correct
13 Correct 261 ms 34276 KB Output is correct
14 Correct 378 ms 44136 KB Output is correct
15 Correct 429 ms 48172 KB Output is correct
16 Correct 135 ms 33228 KB Output is correct
17 Correct 112 ms 33220 KB Output is correct
18 Correct 668 ms 225880 KB Output is correct
19 Correct 694 ms 234716 KB Output is correct
20 Correct 1081 ms 380112 KB Output is correct
21 Correct 521 ms 199256 KB Output is correct
22 Correct 149 ms 39092 KB Output is correct
23 Correct 149 ms 39628 KB Output is correct
24 Correct 626 ms 216648 KB Output is correct