Submission #1256822

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256822		ssitaram	Happiness (Balkan15_HAPPINESS)	C++20	60 / 100	2126 ms	537096 KiB

happiness

#include <bits/stdc++.h>
#include "happiness.h"
using namespace std;

typedef long long ll;

struct Node {
	Node *l, *r;
	ll mn, lazy;

	Node(ll a, ll b) : l(nullptr), r(nullptr), mn(-(b - 1)), lazy(0) {}

	void apply(ll v) {
		mn += v;
		lazy += v;
	}

	void push(ll a, ll b) {
		ll m = (a + b) / 2;
		if (l == nullptr) l = new Node(a, m);
		if (r == nullptr) r = new Node(m, b);
		l->apply(lazy);
		r->apply(lazy);
		lazy = 0;
	}
};

Node* root;
ll sz = 1, n;
map<ll, int> co;

void ch(Node* here, ll l, ll r, ll a, ll b, ll v) {
	if (r <= a || l >= b) return;
	if (a <= l && r <= b) {
		here->apply(v);
		return;
	}
	here->push(l, r);
	ll m = (l + r) / 2;
	ch(here->l, l, m, a, b, v);
	ch(here->r, m, r, a, b, v);
	here->mn = min(here->l->mn, here->r->mn);
}

void ch(ll a, ll b, ll v) {
	ch(root, 0, sz, a, b, v);
}

ll mn(Node* here, ll l, ll r, ll a, ll b) {
	if (r <= a || l >= b) return INT64_MAX;
	if (a <= l && r <= b) return here->mn;
	here->push(l, r);
	ll m = (l + r) / 2;
	return min(mn(here->l, l, m, a, b), mn(here->r, m, r, a, b));
}

bool good() {
	if (co.empty()) return true;
	return mn(root, 0, sz, 1, co.rbegin()->first + 1) >= 0;
}

void add(ll v) {
	++co[v];
	ch(v + 1, n, v);
}

void rem(ll v) {
	if (--co[v] == 0) co.erase(v);
	ch(v + 1, n, -v);
}

bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
	n = maxCoinSize + 1;
	while (sz < n) sz *= 2;
	root = new Node(0, n);
	ch(1, n, 1);
	for (int i = 0; i < coinsCount; ++i) add(coins[i]);
	return good();
}

bool is_happy(int event, int coinsCount, long long coins[]) {
	for (int i = 0; i < coinsCount; ++i) {
		if (event == 1) add(coins[i]);
		else rem(coins[i]);
	}
	return good();
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40