제출 #1256814

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1256814		ssitaram	Happiness (Balkan15_HAPPINESS)	C++20	0 / 100	1 ms	320 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(int a, int b) : l(nullptr), r(nullptr), mn(-(b - 1)), lazy(0) {}

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

	void push(int a, int b) {
		int 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;
multiset<ll> co;

void ch(Node* here, int l, int r, int a, int b, ll v) {
	if (r <= a || l >= b) return;
	if (a <= l && r <= b) {
		here->apply(v);
		return;
	}
	here->push(l, r);
	int 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(int a, int b, ll v) {
	ch(root, 0, sz, a, b, v);
}

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

bool good() {
	return mn(root, 0, sz, 1, *prev(co.end()) + 1) >= 0;
}

void add(ll v) {
	co.insert(v);
	ch(v + 1, n, v);
}

void rem(ll v) {
	co.erase(co.find(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: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40