Submission #278572

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
278572	2020-08-21T14:41:59 Z	arnold518	Happiness (Balkan15_HAPPINESS)	C++14	60 / 100	2000 ms	83384 KB

happiness

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

ll M;

unordered_map<ll, ll> tree;

void update(ll i, ll k) { for(; i<=M; i+=(i&-i)) tree[i]+=k; }
ll query(ll i) { ll ret=0; for(i=min(i, M); i>0; i-=(i&-i)) ret+=tree[i]; return ret; }

void push(ll x)
{
	update(x, x);
}

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

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

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

	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

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	0 ms	256 KB	Output is correct
3	Correct	1 ms	256 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	0 ms	256 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	0 ms	256 KB	Output is correct
3	Correct	1 ms	256 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	0 ms	256 KB	Output is correct
6	Correct	4 ms	1152 KB	Output is correct
7	Correct	5 ms	1280 KB	Output is correct
8	Correct	57 ms	7332 KB	Output is correct
9	Correct	52 ms	7324 KB	Output is correct
10	Correct	48 ms	7332 KB	Output is correct

Subtask #3

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	1 ms	256 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	0 ms	256 KB	Output is correct
6	Correct	604 ms	16696 KB	Output is correct
7	Correct	562 ms	16868 KB	Output is correct
8	Correct	592 ms	16680 KB	Output is correct
9	Correct	963 ms	19756 KB	Output is correct
10	Correct	894 ms	21004 KB	Output is correct
11	Correct	247 ms	15588 KB	Output is correct
12	Correct	234 ms	15604 KB	Output is correct

Subtask #4

0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	1 ms	256 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	0 ms	256 KB	Output is correct
6	Correct	4 ms	1152 KB	Output is correct
7	Correct	5 ms	1280 KB	Output is correct
8	Correct	57 ms	7332 KB	Output is correct
9	Correct	52 ms	7324 KB	Output is correct
10	Correct	48 ms	7332 KB	Output is correct
11	Correct	604 ms	16696 KB	Output is correct
12	Correct	562 ms	16868 KB	Output is correct
13	Correct	592 ms	16680 KB	Output is correct
14	Correct	963 ms	19756 KB	Output is correct
15	Correct	894 ms	21004 KB	Output is correct
16	Correct	247 ms	15588 KB	Output is correct
17	Correct	234 ms	15604 KB	Output is correct
18	Execution timed out	2081 ms	83384 KB	Time limit exceeded
19	Halted	0 ms	0 KB	-