oj.uz

답안 #278572

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
278572 2020-08-21T14:41:59 Z arnold518 Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 2000 ms 83384 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;

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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -