oj.uz

Submission #427564

# Submission time Handle Problem Language Result Execution time Memory
427564 2021-06-14T17:15:00 Z CSQ31 Happiness (Balkan15_HAPPINESS) C++17
100 / 100
 1620 ms 380188 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 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 3 ms 1740 KB Output is correct
7 Correct 3 ms 1996 KB Output is correct
8 Correct 39 ms 14012 KB Output is correct
9 Correct 31 ms 14132 KB Output is correct
10 Correct 29 ms 13716 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 483 ms 37464 KB Output is correct
7 Correct 485 ms 36932 KB Output is correct
8 Correct 485 ms 37444 KB Output is correct
9 Correct 702 ms 48708 KB Output is correct
10 Correct 763 ms 52608 KB Output is correct
11 Correct 175 ms 36992 KB Output is correct
12 Correct 171 ms 37128 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 3 ms 1740 KB Output is correct
7 Correct 3 ms 1996 KB Output is correct
8 Correct 39 ms 14012 KB Output is correct
9 Correct 31 ms 14132 KB Output is correct
10 Correct 29 ms 13716 KB Output is correct
11 Correct 483 ms 37464 KB Output is correct
12 Correct 485 ms 36932 KB Output is correct
13 Correct 485 ms 37444 KB Output is correct
14 Correct 702 ms 48708 KB Output is correct
15 Correct 763 ms 52608 KB Output is correct
16 Correct 175 ms 36992 KB Output is correct
17 Correct 171 ms 37128 KB Output is correct
18 Correct 1093 ms 225904 KB Output is correct
19 Correct 1170 ms 234596 KB Output is correct
20 Correct 1620 ms 380188 KB Output is correct
21 Correct 883 ms 199088 KB Output is correct
22 Correct 226 ms 39048 KB Output is correct
23 Correct 220 ms 39548 KB Output is correct
24 Correct 1127 ms 216700 KB Output is correct