Submission #1268578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268578		uranium235	Happiness (Balkan15_HAPPINESS)	C++17	0 / 100	0 ms	320 KiB

happiness

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

struct node {
	int left, right;
	ll sum, bound;
	void apply(ll x) {
		sum += x;
		bound = sum - 1;
	}
	void merge(node &l, node &r) {
		bound = max(l.bound, r.bound - l.sum);
		sum = l.sum + r.sum;
	}
};

class sparseseg {
	public:
		vector<node> a;
		sparseseg() : a() {
			a.reserve(100000);
			a.push_back({-1, -1, 0, 0});
		}
		void push(int x) {
			// cout << "push " << x << endl;
			if (a[x].left == -1) {
				a[x].left = a.size();
				a.push_back({-1, -1, 0, 0});
			}
			if (a[x].right == -1) {
				a[x].right = a.size();
				a.push_back({-1, -1, 0, 0});
			}
		}
		void upd(ll lll, ll rr, ll l, ll r, int v, ll x) {
			if (r < lll || rr < l) return;
			else if (lll <= l && r <= rr) a[v].apply(x);
			else {
				push(v);
				ll m = (l + r) / 2;
				upd(lll, rr, l, m, a[v].left, x);
				upd(lll, rr, m + 1, r, a[v].right, x);
				a[v].merge(a[a[v].left], a[a[v].right]);
			}
		}
};

sparseseg tree;
node get;
const ll bound = ll(1000000) * 1000000 + 1;

bool init(int coinsCount, ll maxCoinSize, ll coins[]) {
	for (int i = 0; i < coinsCount; i++) tree.upd(coins[i], coins[i], 0, bound, 0, coins[i]);
	// cout << "bound " << tree.a[0].bound << " " << tree.a.size() << endl;
	return tree.a[0].bound <= 0;
}
bool is_happy(int event, int coinsCount, ll coins[]) {
	for (int i = 0; i < coinsCount; i++) tree.upd(coins[i], coins[i], 0, bound, 0, event * coins[i]);
	// cout << "bound " << tree.a[0].bound << endl;
	return tree.a[0].bound <= 0;
}

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