oj.uz

답안 #278571

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
278571 2020-08-21T14:37:45 Z arnold518 Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 2000 ms 84228 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<=MAXN; i+=(i&-i)) tree[i]+=k; }
ll query(ll i) { ll ret=0; for(; 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 1 ms 416 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 416 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 5 ms 1152 KB Output is correct
7 Correct 6 ms 1280 KB Output is correct
8 Correct 75 ms 7656 KB Output is correct
9 Correct 77 ms 7540 KB Output is correct
10 Correct 64 ms 7580 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 416 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 1407 ms 32648 KB Output is correct
7 Correct 1379 ms 32700 KB Output is correct
8 Correct 1460 ms 34712 KB Output is correct
9 Correct 1936 ms 38652 KB Output is correct
10 Correct 1955 ms 42140 KB Output is correct
11 Correct 875 ms 19304 KB Output is correct
12 Correct 843 ms 19688 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 416 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 5 ms 1152 KB Output is correct
7 Correct 6 ms 1280 KB Output is correct
8 Correct 75 ms 7656 KB Output is correct
9 Correct 77 ms 7540 KB Output is correct
10 Correct 64 ms 7580 KB Output is correct
11 Correct 1407 ms 32648 KB Output is correct
12 Correct 1379 ms 32700 KB Output is correct
13 Correct 1460 ms 34712 KB Output is correct
14 Correct 1936 ms 38652 KB Output is correct
15 Correct 1955 ms 42140 KB Output is correct
16 Correct 875 ms 19304 KB Output is correct
17 Correct 843 ms 19688 KB Output is correct
18 Execution timed out 2057 ms 84228 KB Time limit exceeded
19 Halted 0 ms 0 KB -