oj.uz

Submission #278577

# Submission time Handle Problem Language Result Execution time Memory
278577 2020-08-21T14:51:09 Z arnold518 Happiness (Balkan15_HAPPINESS) C++14
100 / 100
 1087 ms 134580 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 MAXN = 1e18;
const int MAXVAL = 8e6;

ll M;

struct Node
{
	ll val;
	int lc, rc;
	Node() : val(0), lc(-1), rc(-1) {}
};
Node nodes[MAXVAL];

int ncnt, root;
int newNode() { return ncnt++; }

void update(int node, ll tl, ll tr, ll p, ll k)
{
	nodes[node].val+=k;
	if(tl==tr) return;
	ll mid=tl+tr>>1;
	if(p<=mid)
	{
		if(nodes[node].lc==-1) nodes[node].lc=newNode();
		update(nodes[node].lc, tl, mid, p, k);
	}
	else
	{
		if(nodes[node].rc==-1) nodes[node].rc=newNode();
		update(nodes[node].rc, mid+1, tr, p, k);
	}
}

ll query(int node, ll tl, ll tr, ll l, ll r)
{
	if(r<tl || tr<l) return 0;
	if(l<=tl && tr<=r) return nodes[node].val;
	ll mid=tl+tr>>1;
	ll ret=0;
	if(nodes[node].lc!=-1) ret+=query(nodes[node].lc, tl, mid, l, r);
	if(nodes[node].rc!=-1) ret+=query(nodes[node].rc, mid+1, tr, l, r);
	return ret;
}

void push(ll x)
{
	update(root, 1, M, x, x);
}

void pop(ll x)
{
	update(root, 1, M, x, -x);
}

bool query()
{
	ll now=1;
	ll sum=query(root, 1, M, 1, M);
	while(now<sum)
	{
		ll t=query(root, 1, M, 1, now);
		if(t<now) return 0;
		now=t+1;
	}
	return 1;
}

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

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

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

Compilation message

happiness.cpp: In function 'void update(int, ll, ll, ll, ll)':
happiness.cpp:29:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |  ll mid=tl+tr>>1;
      |         ~~^~~
happiness.cpp: In function 'll query(int, ll, ll, ll, ll)':
happiness.cpp:46:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |  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 102 ms 125560 KB Output is correct
2 Correct 77 ms 125560 KB Output is correct
3 Correct 77 ms 125560 KB Output is correct
4 Correct 78 ms 125560 KB Output is correct
5 Correct 76 ms 125560 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 125560 KB Output is correct
2 Correct 77 ms 125560 KB Output is correct
3 Correct 77 ms 125560 KB Output is correct
4 Correct 78 ms 125560 KB Output is correct
5 Correct 76 ms 125560 KB Output is correct
6 Correct 77 ms 125560 KB Output is correct
7 Correct 79 ms 125560 KB Output is correct
8 Correct 92 ms 125816 KB Output is correct
9 Correct 92 ms 125816 KB Output is correct
10 Correct 92 ms 125816 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 125560 KB Output is correct
2 Correct 77 ms 125560 KB Output is correct
3 Correct 77 ms 125560 KB Output is correct
4 Correct 78 ms 125560 KB Output is correct
5 Correct 76 ms 125560 KB Output is correct
6 Correct 419 ms 128504 KB Output is correct
7 Correct 425 ms 127736 KB Output is correct
8 Correct 461 ms 127736 KB Output is correct
9 Correct 652 ms 127608 KB Output is correct
10 Correct 563 ms 127736 KB Output is correct
11 Correct 223 ms 126872 KB Output is correct
12 Correct 224 ms 126908 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 125560 KB Output is correct
2 Correct 77 ms 125560 KB Output is correct
3 Correct 77 ms 125560 KB Output is correct
4 Correct 78 ms 125560 KB Output is correct
5 Correct 76 ms 125560 KB Output is correct
6 Correct 77 ms 125560 KB Output is correct
7 Correct 79 ms 125560 KB Output is correct
8 Correct 92 ms 125816 KB Output is correct
9 Correct 92 ms 125816 KB Output is correct
10 Correct 92 ms 125816 KB Output is correct
11 Correct 419 ms 128504 KB Output is correct
12 Correct 425 ms 127736 KB Output is correct
13 Correct 461 ms 127736 KB Output is correct
14 Correct 652 ms 127608 KB Output is correct
15 Correct 563 ms 127736 KB Output is correct
16 Correct 223 ms 126872 KB Output is correct
17 Correct 224 ms 126908 KB Output is correct
18 Correct 840 ms 129544 KB Output is correct
19 Correct 893 ms 132088 KB Output is correct
20 Correct 1087 ms 134580 KB Output is correct
21 Correct 612 ms 131576 KB Output is correct
22 Correct 276 ms 131516 KB Output is correct
23 Correct 289 ms 132216 KB Output is correct
24 Correct 874 ms 132040 KB Output is correct