oj.uz

Submission #1041902

# Submission time Handle Problem Language Result Execution time Memory
1041902 2024-08-02T09:50:40 Z Thunnus Happiness (Balkan15_HAPPINESS) C++17
100 / 100
 838 ms 380160 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 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 1884 KB Output is correct
7 Correct 1 ms 1980 KB Output is correct
8 Correct 15 ms 14168 KB Output is correct
9 Correct 17 ms 14172 KB Output is correct
10 Correct 15 ms 13808 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 200 ms 37460 KB Output is correct
7 Correct 190 ms 36936 KB Output is correct
8 Correct 212 ms 37616 KB Output is correct
9 Correct 296 ms 48832 KB Output is correct
10 Correct 305 ms 52560 KB Output is correct
11 Correct 89 ms 36944 KB Output is correct
12 Correct 95 ms 37204 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 1884 KB Output is correct
7 Correct 1 ms 1980 KB Output is correct
8 Correct 15 ms 14168 KB Output is correct
9 Correct 17 ms 14172 KB Output is correct
10 Correct 15 ms 13808 KB Output is correct
11 Correct 200 ms 37460 KB Output is correct
12 Correct 190 ms 36936 KB Output is correct
13 Correct 212 ms 37616 KB Output is correct
14 Correct 296 ms 48832 KB Output is correct
15 Correct 305 ms 52560 KB Output is correct
16 Correct 89 ms 36944 KB Output is correct
17 Correct 95 ms 37204 KB Output is correct
18 Correct 538 ms 225976 KB Output is correct
19 Correct 567 ms 234616 KB Output is correct
20 Correct 838 ms 380160 KB Output is correct
21 Correct 434 ms 199252 KB Output is correct
22 Correct 122 ms 39244 KB Output is correct
23 Correct 110 ms 39600 KB Output is correct
24 Correct 524 ms 216692 KB Output is correct