Submission #278094

#	Time	Username	Problem	Language	Result	Execution time	Memory
278094		arnold518	Happiness (Balkan15_HAPPINESS)	C++14	60 / 100	2095 ms	430744 KiB

happiness

#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll INF = 1e18;
const int MAXVAL = 8e6;

ll M;
map<ll, int> MM;

struct Node
{
	ll val, lazy, pl, pr;
	int lc, rc;
	Node() : val(0), lazy(0), lc(-1), rc(-1), pl(-1), pr(-1) {} 
};

Node nodes[MAXVAL];
int ncnt;

int newNode()
{
	return ncnt++;
}

void update(int node, ll tl, ll tr, ll l, ll r, ll k)
{
	if(r<tl || tr<l) return;
	if(l<=tl && tr<=r)
	{
		nodes[node].lazy+=k;
		return;
	}
	ll mid=tl+tr>>1;

	if(nodes[node].pl!=-1)
	{
		if(nodes[node].pl<=mid)
		{
			nodes[node].lc=newNode();
			ll ql=nodes[node].pl, qr=min(mid, nodes[node].pr);
			if(ql==tl && qr==mid)
			{
				nodes[nodes[node].lc].lazy=nodes[node].val;
			}
			else
			{
				nodes[nodes[node].lc].pl=ql;
				nodes[nodes[node].lc].pr=qr;
				nodes[nodes[node].lc].val=nodes[node].val;
			}
		}
		if(mid+1<=nodes[node].pr)
		{
			nodes[node].rc=newNode();
			ll ql=max(mid+1, nodes[node].pl), qr=nodes[node].pr;
			if(ql==mid+1 && qr==tr)
			{
				nodes[nodes[node].rc].lazy=nodes[node].val;
			}
			else
			{
				nodes[nodes[node].rc].pl=ql;
				nodes[nodes[node].rc].pr=qr;	
				nodes[nodes[node].rc].val=nodes[node].val;
			}
		}
		nodes[node].pl=-1; nodes[node].pr=-1;
		nodes[node].val=min(nodes[node].val, 0ll);
	}

	if(l<=mid)
	{
		if(nodes[node].lc==-1)
		{
			nodes[node].lc=newNode();
			nodes[nodes[node].lc].pl=l;
			nodes[nodes[node].lc].pr=min(mid, r);
			nodes[nodes[node].lc].val=k;
		}
		else
		{
			update(nodes[node].lc, tl, mid, l, min(mid, r), k);
		}
	}
	if(mid+1<=r)
	{
		if(nodes[node].rc==-1)
		{
			nodes[node].rc=newNode();
			nodes[nodes[node].rc].pl=max(mid+1, l);
			nodes[nodes[node].rc].pr=r;
			nodes[nodes[node].rc].val=k;
		}
		else
		{
			update(nodes[node].rc, mid+1, tr, max(mid+1, l), r, k);
		}
	}

	nodes[node].val=INF;
	if(nodes[node].lc!=-1) nodes[node].val=min(nodes[node].val, nodes[nodes[node].lc].val+nodes[nodes[node].lc].lazy);
	if(nodes[node].rc!=-1) nodes[node].val=min(nodes[node].val, nodes[nodes[node].rc].val+nodes[nodes[node].rc].lazy);
}

int root;

ll query()
{
	return nodes[root].val+nodes[root].lazy;
}

void push(ll x)
{
	update(root, 1, M, x+1, M, x);
	MM[x]++;
	if(MM[x]==1)
	{
		auto it=MM.find(x);
		ll val=-x;
		if(next(it)!=MM.end()) val+=next(it)->first;
		update(root, 1, M, prev(it)->first+1, x, val);
	}
}

void pop(ll x)
{
	update(root, 1, M, x+1, M, -x);
	MM[x]--;
	if(MM[x]==0)
	{
		auto it=MM.find(x);
		ll val=x;
		if(next(it)!=MM.end()) val-=next(it)->first;
		update(root, 1, M, prev(it)->first+1, x, val);
		MM.erase(x);
	}
}

bool init(int coinsCount, ll maxCoinSize, ll coins[])
{
	M=maxCoinSize;
	root=newNode();
	MM[0];

	for(int i=0; i<coinsCount; i++) push(coins[i]);
	return query()>=-1;
}

bool is_happy(int event, int coinsCount, ll coins[])
{
	if(event == -1) for(int i=0; i<coinsCount; i++) pop(coins[i]);
	else for(int i=0; i<coinsCount; i++) push(coins[i]);
	return query()>=-1;
}

Compilation message (stderr)

happiness.cpp: In constructor 'Node::Node()':
happiness.cpp:22:10: warning: 'Node::rc' will be initialized after [-Wreorder]
   22 |  int lc, rc;
      |          ^~
happiness.cpp:21:16: warning:   'll Node::pl' [-Wreorder]
   21 |  ll val, lazy, pl, pr;
      |                ^~
happiness.cpp:23:2: warning:   when initialized here [-Wreorder]
   23 |  Node() : val(0), lazy(0), lc(-1), rc(-1), pl(-1), pr(-1) {}
      |  ^~~~
happiness.cpp: In function 'void update(int, ll, ll, ll, ll, ll)':
happiness.cpp:42:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |  ll mid=tl+tr>>1;
      |         ~~^~~
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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40