oj.uz

Submission #277834

# Submission time Handle Problem Language Result Execution time Memory
277834 2020-08-21T07:41:01 Z arnold518 Happiness (Balkan15_HAPPINESS) C++14
10 / 100
 550 ms 104044 KB 
#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;

ll M;
map<ll, int> MM;

struct Node
{
	ll val, lazy;
	Node *lc, *rc;
	Node() : val(0), lazy(0) {} 
};

void busy(Node *node, ll tl, ll tr)
{
	if(node->lazy==0) return;
	node->val+=node->lazy;
	if(tl!=tr)
	{
		if(node->lc==NULL) node->lc=new Node();
		node->lc->lazy+=node->lazy;
		if(node->rc==NULL) node->rc=new Node();
		node->rc->lazy+=node->lazy;
	}
	node->lazy=0;
}

void update(Node *node, ll tl, ll tr, ll l, ll r, ll k)
{
	busy(node, tl, tr);
	if(r<tl || tr<l) return;
	if(l<=tl && tr<=r)
	{
		node->lazy+=k;
		busy(node, tl, tr);
		return;
	}
	ll mid=tl+tr>>1;
	if(node->lc==NULL) node->lc=new Node();
	if(node->rc==NULL) node->rc=new Node();
	update(node->lc, tl, mid, l, r, k);
	update(node->rc, mid+1, tr, l, r, k);

	node->val=INF;
	node->val=min(node->val, node->lc->val+node->lc->lazy);
	node->val=min(node->val, node->rc->val+node->rc->lazy);
}

Node *root;

ll query()
{
	return root->val+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=new Node();
	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(Node*, ll, ll, ll, ll, ll)':
happiness.cpp:45:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |  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 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Runtime error 20 ms 11776 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Runtime error 550 ms 104044 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Runtime error 20 ms 11776 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -