oj.uz

Submission #277984

# Submission time Handle Problem Language Result Execution time Memory
277984 2020-08-21T08:24:08 Z arnold518 Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 2000 ms 464088 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;
	int lc, rc;
	Node() : val(0), lazy(0), lc(-1), rc(-1) {} 
};

Node nodes[MAXVAL];
vector<int> pool;

int newNode()
{
	int t=pool.back(); pool.pop_back();
	return t;
}

void deleteNode(int node)
{
	pool.push_back(node);
	nodes[node]=Node();
}	

void busy(int node, ll tl, ll tr)
{
	if(nodes[node].lazy==0) return;
	nodes[node].val+=nodes[node].lazy;
	if(tl!=tr)
	{
		if(nodes[node].lc==-1) nodes[node].lc=newNode();
		nodes[nodes[node].lc].lazy+=nodes[node].lazy;
		if(nodes[node].rc==-1) nodes[node].rc=newNode();
		nodes[nodes[node].rc].lazy+=nodes[node].lazy;
	}
	nodes[node].lazy=0;
}

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;
	}

	busy(node, tl, tr);
	ll mid=tl+tr>>1;

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

	nodes[node].val=INF;
	nodes[node].val=min(nodes[node].val, nodes[nodes[node].lc].val+nodes[nodes[node].lc].lazy);
	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[])
{	
	for(int i=0; i<MAXVAL; i++) pool.push_back(i);
	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 function 'void update(int, ll, ll, ll, ll, ll)':
happiness.cpp:65:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |  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 221300 KB Output is correct
2 Correct 164 ms 221144 KB Output is correct
3 Correct 169 ms 221256 KB Output is correct
4 Correct 165 ms 221136 KB Output is correct
5 Correct 167 ms 221276 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 221300 KB Output is correct
2 Correct 164 ms 221144 KB Output is correct
3 Correct 169 ms 221256 KB Output is correct
4 Correct 165 ms 221136 KB Output is correct
5 Correct 167 ms 221276 KB Output is correct
6 Correct 179 ms 221260 KB Output is correct
7 Correct 174 ms 221116 KB Output is correct
8 Correct 217 ms 221260 KB Output is correct
9 Correct 217 ms 221268 KB Output is correct
10 Correct 207 ms 221264 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 221300 KB Output is correct
2 Correct 164 ms 221144 KB Output is correct
3 Correct 169 ms 221256 KB Output is correct
4 Correct 165 ms 221136 KB Output is correct
5 Correct 167 ms 221276 KB Output is correct
6 Correct 1105 ms 226456 KB Output is correct
7 Correct 1082 ms 226480 KB Output is correct
8 Correct 1096 ms 226584 KB Output is correct
9 Correct 1763 ms 227224 KB Output is correct
10 Correct 1852 ms 234136 KB Output is correct
11 Correct 815 ms 236184 KB Output is correct
12 Correct 851 ms 236312 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 221300 KB Output is correct
2 Correct 164 ms 221144 KB Output is correct
3 Correct 169 ms 221256 KB Output is correct
4 Correct 165 ms 221136 KB Output is correct
5 Correct 167 ms 221276 KB Output is correct
6 Correct 179 ms 221260 KB Output is correct
7 Correct 174 ms 221116 KB Output is correct
8 Correct 217 ms 221260 KB Output is correct
9 Correct 217 ms 221268 KB Output is correct
10 Correct 207 ms 221264 KB Output is correct
11 Correct 1105 ms 226456 KB Output is correct
12 Correct 1082 ms 226480 KB Output is correct
13 Correct 1096 ms 226584 KB Output is correct
14 Correct 1763 ms 227224 KB Output is correct
15 Correct 1852 ms 234136 KB Output is correct
16 Correct 815 ms 236184 KB Output is correct
17 Correct 851 ms 236312 KB Output is correct
18 Execution timed out 2117 ms 464088 KB Time limit exceeded
19 Halted 0 ms 0 KB -