oj.uz

Submission #280480

# Submission time Handle Problem Language Result Execution time Memory
280480 2020-08-22T20:09:05 Z dolphingarlic Happiness (Balkan15_HAPPINESS) C++14
100 / 100
 1557 ms 372296 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 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 3 ms 1792 KB Output is correct
7 Correct 4 ms 1920 KB Output is correct
8 Correct 33 ms 13952 KB Output is correct
9 Correct 31 ms 14080 KB Output is correct
10 Correct 28 ms 13568 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 494 ms 34424 KB Output is correct
7 Correct 497 ms 34080 KB Output is correct
8 Correct 528 ms 34460 KB Output is correct
9 Correct 729 ms 44264 KB Output is correct
10 Correct 764 ms 48288 KB Output is correct
11 Correct 174 ms 33320 KB Output is correct
12 Correct 172 ms 33400 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 3 ms 1792 KB Output is correct
7 Correct 4 ms 1920 KB Output is correct
8 Correct 33 ms 13952 KB Output is correct
9 Correct 31 ms 14080 KB Output is correct
10 Correct 28 ms 13568 KB Output is correct
11 Correct 494 ms 34424 KB Output is correct
12 Correct 497 ms 34080 KB Output is correct
13 Correct 528 ms 34460 KB Output is correct
14 Correct 729 ms 44264 KB Output is correct
15 Correct 764 ms 48288 KB Output is correct
16 Correct 174 ms 33320 KB Output is correct
17 Correct 172 ms 33400 KB Output is correct
18 Correct 1103 ms 220500 KB Output is correct
19 Correct 1166 ms 229392 KB Output is correct
20 Correct 1557 ms 372296 KB Output is correct
21 Correct 852 ms 194424 KB Output is correct
22 Correct 217 ms 33400 KB Output is correct
23 Correct 221 ms 33400 KB Output is correct
24 Correct 1085 ms 211704 KB Output is correct