Submission #1189837

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189837		12345678	Happiness (Balkan15_HAPPINESS)	C++20	0 / 100	0 ms	320 KiB

happiness

#include "happiness.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll nx=1e12, inf=1e18;

multiset<ll> ms;

struct sparsesegtree
{
	struct node
	{
		ll mx, lz;
		node *l, *r;
		node(): mx(-inf), lz(0){}
	};
	typedef node* pnode;
	pnode rt=new node();
	void apply(pnode &k, ll vl)
	{
		if (!k) k=new node();
		k->mx+=vl;
		k->lz+=vl;
	}
	void pushlz(pnode &k)
	{
		apply(k->l, k->lz);
		apply(k->r, k->lz);
		k->lz=0;
	}
	void update(ll l, ll r, pnode &k, ll ql, ll qr, ll vl)
	{
		//cout<<"debug "<<l<<' '<<r<<'\n';
		if (!k)
		{
			while (1)
			{
				
			}
		}
		if (qr<l||r<ql||qr<ql) return;
		if (ql<=l&&r<=qr) return apply(k, vl);
		ll md=(l+r)/2;
		pushlz(k);
		update(l, md, k->l, ql, qr, vl);
		update(md+1, r, k->r, ql, qr, vl);
		k->mx=max(k->l->mx, k->r->mx);
	}
} s;

void add(ll x)
{
	if (ms.find(x)==ms.end()) s.update(1, inf, s.rt, x, x, inf+x);
	ms.insert(x);
	s.update(1, inf, s.rt, x+1, inf, -x);
}

void rem(ll x)
{
	s.update(1, inf, s.rt, x+1, inf, +x);
	ms.erase(ms.find(x));
	if (ms.find(x)==ms.end()) s.update(1, inf, s.rt, x, x, -inf-x);
}

bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
	for (int i=0; i<coinsCount; i++) add(coins[i]);
	//cout<<"after "<<s.rt->mx<<'\n';
	if (ms.empty()) return 1;
	return ((*ms.begin())==1)&&(s.rt->mx<=1);
}

bool is_happy(int event, int coinsCount, long long coins[]) {
	for (int i=0; i<coinsCount; i++)
	{
		if (event==-1) rem(coins[i]);
		else add(coins[i]);
	}
	//cout<<"after "<<s.rt->mx<<'\n';
	if (ms.empty()) return 1;
	return ((*ms.begin())==1)&&(s.rt->mx<=1);
}

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