oj.uz

Submission #925159

# Submission time Handle Problem Language Result Execution time Memory
925159 2024-02-10T21:52:34 Z myst6 Happiness (Balkan15_HAPPINESS) C++14
100 / 100
 884 ms 256500 KB 
#include "happiness.h"
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
struct Node {
	ll sum;
	Node *left, *right;
	Node() : sum(0), left(nullptr), right(nullptr) {}
	void update(ll v, ll xl, ll xr, ll delta) {
		sum += delta;
		if (xl == xr) return;
		ll xm = (xl + xr) / 2;
		if (v <= xm) {
			if (!left) left = new Node();
			left->update(v, xl, xm, delta);
		} else {
			if (!right) right = new Node();
			right->update(v, xm+1, xr, delta);
		}
	}
	ll query(ll l, ll r, ll xl, ll xr) {
		if (l > r) return 0;
		if (l == xl && r == xr) {
			return sum;
		} else {
			ll xm = (xl + xr) / 2;
			ll ans = 0;
			if (left) ans += left->query(l, min(r, xm), xl, xm);
			if (right) ans += right->query(max(l, xm+1), r, xm+1, xr);
			return ans;
		}
	}
} tree;
 
const ll hi = 1'000'000'000'005LL;
 
void add(ll coin) {
	tree.update(coin, 1, hi, +coin);
}
 
void remove(ll coin) {
	tree.update(coin, 1, hi, -coin);
}
 
bool check() {
	ll curr = 1;
	while (curr < min(hi, tree.sum)) {
		ll sum = tree.query(1, curr, 1, hi);
		if (sum < curr) return false;
		curr = sum + 1;
	}
	return true;
}
 
bool init(int coinsCount, ll maxCoinSize, ll coins[]) {
	for (int i=0; i<coinsCount; i++) add(coins[i]);
	return check();
}
 
bool is_happy(int event, int coinsCount, ll coins[]) {
	for (int i=0; i<coinsCount; i++) 
		if (event == 1) add(coins[i]);
		else remove(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 600 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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 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 3 ms 1372 KB Output is correct
7 Correct 3 ms 1372 KB Output is correct
8 Correct 16 ms 9308 KB Output is correct
9 Correct 16 ms 9564 KB Output is correct
10 Correct 15 ms 9240 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 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 285 ms 23332 KB Output is correct
7 Correct 279 ms 23244 KB Output is correct
8 Correct 298 ms 23392 KB Output is correct
9 Correct 400 ms 30032 KB Output is correct
10 Correct 370 ms 32596 KB Output is correct
11 Correct 140 ms 22444 KB Output is correct
12 Correct 132 ms 22344 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 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 3 ms 1372 KB Output is correct
7 Correct 3 ms 1372 KB Output is correct
8 Correct 16 ms 9308 KB Output is correct
9 Correct 16 ms 9564 KB Output is correct
10 Correct 15 ms 9240 KB Output is correct
11 Correct 285 ms 23332 KB Output is correct
12 Correct 279 ms 23244 KB Output is correct
13 Correct 298 ms 23392 KB Output is correct
14 Correct 400 ms 30032 KB Output is correct
15 Correct 370 ms 32596 KB Output is correct
16 Correct 140 ms 22444 KB Output is correct
17 Correct 132 ms 22344 KB Output is correct
18 Correct 579 ms 147368 KB Output is correct
19 Correct 607 ms 153168 KB Output is correct
20 Correct 884 ms 256500 KB Output is correct
21 Correct 474 ms 134996 KB Output is correct
22 Correct 134 ms 28360 KB Output is correct
23 Correct 139 ms 28676 KB Output is correct
24 Correct 566 ms 146748 KB Output is correct