oj.uz

Submission #277839

# Submission time Handle Problem Language Result Execution time Memory
277839 2020-08-21T07:42:08 Z arnold518 Happiness (Balkan15_HAPPINESS) C++14
30 / 100
 2000 ms 82036 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), lc(NULL), rc(NULL) {} 
};

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
20.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 Correct 12 ms 6016 KB Output is correct
7 Correct 13 ms 6528 KB Output is correct
8 Correct 148 ms 50168 KB Output is correct
9 Correct 164 ms 50680 KB Output is correct
10 Correct 124 ms 49016 KB Output is correct

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 Correct 1414 ms 66988 KB Output is correct
7 Correct 1323 ms 66956 KB Output is correct
8 Correct 1402 ms 67660 KB Output is correct
9 Execution timed out 2070 ms 82036 KB Time limit exceeded
10 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 Correct 12 ms 6016 KB Output is correct
7 Correct 13 ms 6528 KB Output is correct
8 Correct 148 ms 50168 KB Output is correct
9 Correct 164 ms 50680 KB Output is correct
10 Correct 124 ms 49016 KB Output is correct
11 Correct 1414 ms 66988 KB Output is correct
12 Correct 1323 ms 66956 KB Output is correct
13 Correct 1402 ms 67660 KB Output is correct
14 Execution timed out 2070 ms 82036 KB Time limit exceeded
15 Halted 0 ms 0 KB -