oj.uz

Submission #674257

# Submission time Handle Problem Language Result Execution time Memory
674257 2022-12-23T15:09:06 Z kirakaminski968 Happiness (Balkan15_HAPPINESS) C++17
100 / 100
 1164 ms 380264 KB 
#include "happiness.h"
struct Node {
	long long l, r, val;
	Node *lc, *rc;
	Node(long long L, long long R): l(L), r(R), val(0), lc(nullptr), rc(nullptr) {}
	void update(long long p, long long v) {
		val += v;
		if (l != r) {
			long long mid = (l + r) / 2;
			if (p > mid) {
				if (!rc) rc = new Node(mid + 1, r);
				rc->update(p, v);
			} else {
				if (!lc) lc = new Node(l, mid);
				lc->update(p, v);
			}
		}
	}
	long long query(long long a, long long b) {
		if (r < a || l > b) return 0;
		if (r <= b && l >= a) return val;
		long long ret = 0;
		if (lc) ret += lc->query(a, b);
		if (rc) ret += rc->query(a, b);
		return ret;
	}
};
Node *root;

bool check() {
	long long curr = 1, sm = root->val;
	while (curr < sm) {
		long long t = root->query(1, curr);
		if (t < curr) return false;
		curr = t + 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], event * coins[i]);
	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 308 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 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 308 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 1748 KB Output is correct
7 Correct 3 ms 1876 KB Output is correct
8 Correct 28 ms 14064 KB Output is correct
9 Correct 24 ms 14236 KB Output is correct
10 Correct 21 ms 13696 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 308 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 362 ms 37524 KB Output is correct
7 Correct 352 ms 37024 KB Output is correct
8 Correct 406 ms 37508 KB Output is correct
9 Correct 497 ms 48712 KB Output is correct
10 Correct 518 ms 52772 KB Output is correct
11 Correct 143 ms 36940 KB Output is correct
12 Correct 143 ms 37060 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 308 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 1748 KB Output is correct
7 Correct 3 ms 1876 KB Output is correct
8 Correct 28 ms 14064 KB Output is correct
9 Correct 24 ms 14236 KB Output is correct
10 Correct 21 ms 13696 KB Output is correct
11 Correct 362 ms 37524 KB Output is correct
12 Correct 352 ms 37024 KB Output is correct
13 Correct 406 ms 37508 KB Output is correct
14 Correct 497 ms 48712 KB Output is correct
15 Correct 518 ms 52772 KB Output is correct
16 Correct 143 ms 36940 KB Output is correct
17 Correct 143 ms 37060 KB Output is correct
18 Correct 910 ms 225796 KB Output is correct
19 Correct 891 ms 234696 KB Output is correct
20 Correct 1164 ms 380264 KB Output is correct
21 Correct 676 ms 199308 KB Output is correct
22 Correct 181 ms 39108 KB Output is correct
23 Correct 189 ms 39620 KB Output is correct
24 Correct 838 ms 216772 KB Output is correct