Submission #925158

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
925158	2024-02-10T21:37:33 Z	myst6	Happiness (Balkan15_HAPPINESS)	C++14	60 / 100	1637 ms	524288 KB

happiness

#include "happiness.h"
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
struct Node {
	ll tag, mx;
	Node *left, *right;
	Node() : tag(0), mx(0), left(nullptr), right(nullptr) {}
	void extend(ll xl, ll xr) {
		if (xl != xr && !left) {
			left = new Node();
			right = new Node();
		}
	}
	void apply(ll xl, ll xr) {
		extend(xl, xr);
		if (tag != 0) {
			mx += tag;
			if (left) left->tag += tag;
			if (right) right->tag += tag;
			tag = 0;
		}
	}
	void update(ll l, ll r, ll xl, ll xr, ll delta) {
		if (l > r) return;
		if (l == xl && r == xr) {
			tag += delta;
		} else {
			apply(xl, xr);
			ll xm = (xl + xr) / 2;
			left->update(l, min(r, xm), xl, xm, delta);
			right->update(max(l, xm+1), r, xm+1, xr, delta);
			left->apply(xl, xm); right->apply(xm+1, xr);
			mx = max(left->mx, right->mx);
		}
	}
} tree;
 
const ll hi = 1'000'000'000'005LL;
 
map<ll,int> cnt;
 
void add(ll coin) {
	cnt[coin] += 1;
	if (cnt[coin] == 1) tree.update(coin, coin, 1, hi, +coin);
	tree.update(coin+1, hi, 1, hi, -coin);
}
 
void remove(ll coin) {
	cnt[coin] -= 1;
	if (cnt[coin] == 0) {
		tree.update(coin, coin, 1, hi, -coin);
		cnt.erase(coin);
	}
	tree.update(coin+1, hi, 1, hi, +coin);
}
 
bool check() {
	tree.apply(1, hi);
	return tree.mx <= 1;
}
 
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	1 ms	344 KB	Output is correct
2	Correct	0 ms	600 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	600 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	6 ms	5980 KB	Output is correct
7	Correct	7 ms	6488 KB	Output is correct
8	Correct	65 ms	51100 KB	Output is correct
9	Correct	68 ms	51420 KB	Output is correct
10	Correct	59 ms	49840 KB	Output is correct

Subtask #3

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	600 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	884 ms	70632 KB	Output is correct
7	Correct	865 ms	69768 KB	Output is correct
8	Correct	882 ms	70132 KB	Output is correct
9	Correct	1509 ms	83804 KB	Output is correct
10	Correct	1637 ms	92372 KB	Output is correct
11	Correct	639 ms	47388 KB	Output is correct
12	Correct	599 ms	47784 KB	Output is correct

Subtask #4

0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	600 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	6 ms	5980 KB	Output is correct
7	Correct	7 ms	6488 KB	Output is correct
8	Correct	65 ms	51100 KB	Output is correct
9	Correct	68 ms	51420 KB	Output is correct
10	Correct	59 ms	49840 KB	Output is correct
11	Correct	884 ms	70632 KB	Output is correct
12	Correct	865 ms	69768 KB	Output is correct
13	Correct	882 ms	70132 KB	Output is correct
14	Correct	1509 ms	83804 KB	Output is correct
15	Correct	1637 ms	92372 KB	Output is correct
16	Correct	639 ms	47388 KB	Output is correct
17	Correct	599 ms	47784 KB	Output is correct
18	Runtime error	1178 ms	524288 KB	Execution killed with signal 9
19	Halted	0 ms	0 KB	-