oj.uz

Submission #278094

# Submission time Handle Problem Language Result Execution time Memory
278094 2020-08-21T10:11:10 Z arnold518 Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 2000 ms 430744 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 313432 KB Output is correct
2 Correct 167 ms 313464 KB Output is correct
3 Correct 166 ms 313464 KB Output is correct
4 Correct 166 ms 313464 KB Output is correct
5 Correct 179 ms 313464 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 313432 KB Output is correct
2 Correct 167 ms 313464 KB Output is correct
3 Correct 166 ms 313464 KB Output is correct
4 Correct 166 ms 313464 KB Output is correct
5 Correct 179 ms 313464 KB Output is correct
6 Correct 170 ms 313464 KB Output is correct
7 Correct 184 ms 313592 KB Output is correct
8 Correct 227 ms 314396 KB Output is correct
9 Correct 214 ms 314376 KB Output is correct
10 Correct 220 ms 314232 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 313432 KB Output is correct
2 Correct 167 ms 313464 KB Output is correct
3 Correct 166 ms 313464 KB Output is correct
4 Correct 166 ms 313464 KB Output is correct
5 Correct 179 ms 313464 KB Output is correct
6 Correct 1199 ms 321400 KB Output is correct
7 Correct 1105 ms 321448 KB Output is correct
8 Correct 1221 ms 321400 KB Output is correct
9 Correct 1886 ms 321528 KB Output is correct
10 Correct 1947 ms 325132 KB Output is correct
11 Correct 820 ms 327800 KB Output is correct
12 Correct 898 ms 327672 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 313432 KB Output is correct
2 Correct 167 ms 313464 KB Output is correct
3 Correct 166 ms 313464 KB Output is correct
4 Correct 166 ms 313464 KB Output is correct
5 Correct 179 ms 313464 KB Output is correct
6 Correct 170 ms 313464 KB Output is correct
7 Correct 184 ms 313592 KB Output is correct
8 Correct 227 ms 314396 KB Output is correct
9 Correct 214 ms 314376 KB Output is correct
10 Correct 220 ms 314232 KB Output is correct
11 Correct 1199 ms 321400 KB Output is correct
12 Correct 1105 ms 321448 KB Output is correct
13 Correct 1221 ms 321400 KB Output is correct
14 Correct 1886 ms 321528 KB Output is correct
15 Correct 1947 ms 325132 KB Output is correct
16 Correct 820 ms 327800 KB Output is correct
17 Correct 898 ms 327672 KB Output is correct
18 Execution timed out 2095 ms 430744 KB Time limit exceeded
19 Halted 0 ms 0 KB -