oj.uz

Submission #925139

# Submission time Handle Problem Language Result Execution time Memory
925139 2024-02-10T20:52:50 Z myst6 Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 1610 ms 524288 KB 
#include "happiness.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

// segment tree of a[i] - a[i-1] - a[i-2] - ... - a[1]
// maximum of this must be zero or less
// when adding a[i], update range [a[i], a[i]] with +a[i]
// and updating range [a[i]+1,inf] with -a[i]
// and do the opposite when removing

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);
	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 1 ms 348 KB Output is correct
3 Correct 1 ms 440 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 1 ms 348 KB Output is correct
3 Correct 1 ms 440 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 8 ms 5980 KB Output is correct
7 Correct 9 ms 6748 KB Output is correct
8 Correct 69 ms 51540 KB Output is correct
9 Correct 65 ms 51812 KB Output is correct
10 Correct 61 ms 50000 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 1 ms 348 KB Output is correct
3 Correct 1 ms 440 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1018 ms 82772 KB Output is correct
7 Correct 927 ms 81912 KB Output is correct
8 Correct 963 ms 83028 KB Output is correct
9 Correct 1555 ms 100256 KB Output is correct
10 Correct 1610 ms 106036 KB Output is correct
11 Correct 556 ms 59140 KB Output is correct
12 Correct 544 ms 59168 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 1 ms 348 KB Output is correct
3 Correct 1 ms 440 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 8 ms 5980 KB Output is correct
7 Correct 9 ms 6748 KB Output is correct
8 Correct 69 ms 51540 KB Output is correct
9 Correct 65 ms 51812 KB Output is correct
10 Correct 61 ms 50000 KB Output is correct
11 Correct 1018 ms 82772 KB Output is correct
12 Correct 927 ms 81912 KB Output is correct
13 Correct 963 ms 83028 KB Output is correct
14 Correct 1555 ms 100256 KB Output is correct
15 Correct 1610 ms 106036 KB Output is correct
16 Correct 556 ms 59140 KB Output is correct
17 Correct 544 ms 59168 KB Output is correct
18 Runtime error 1152 ms 524288 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -