oj.uz

Submission #1092119

# Submission time Handle Problem Language Result Execution time Memory
1092119 2024-09-23T08:57:40 Z vijaygomathinayagam Happiness (Balkan15_HAPPINESS) C++17
40 / 100
 387 ms 524288 KB 
#include "happiness.h"

struct Node {
	long long l, r, sum;
	Node* lc, * rc;

	Node(long long l, long long r) : l(l), r(r), sum(0), lc(nullptr), rc(nullptr) {}

	void update(long long p, long long v) {
		sum += v;
		if (l != r) {
			int mid = (l + r) / 2;
			if (p <= mid) {
				if (lc == nullptr)
					lc = new Node(l, mid);
				lc->update(p, v);
			}
			else {
				if (rc == nullptr)
					rc = new Node(mid + 1, r);
				rc->update(p, v);
			}
		}
	}

	long long query(long long a, long long b) {
		if (l >= a && r <= b)
			return sum;
		int mid = (l + r) / 2;
		long long total = 0;
		if (a <= mid && lc != nullptr)
			total += lc->query(a, b);
		if (b >= mid + 1 && rc != nullptr)
			total += rc->query(a, b);
		return total;
	}
};

Node* root;

bool check() {
	long long curr = 1, sum = root->sum;
	while (curr < sum) {
		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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Runtime error 338 ms 524288 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 225 ms 37456 KB Output is correct
7 Correct 217 ms 37148 KB Output is correct
8 Correct 227 ms 37456 KB Output is correct
9 Correct 333 ms 48792 KB Output is correct
10 Correct 387 ms 52768 KB Output is correct
11 Correct 104 ms 36940 KB Output is correct
12 Correct 117 ms 37200 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Runtime error 338 ms 524288 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -