oj.uz

Submission #276430

# Submission time Handle Problem Language Result Execution time Memory
276430 2020-08-20T12:46:57 Z sjimed Happiness (Balkan15_HAPPINESS) C++14
100 / 100
 1366 ms 323136 KB 
#include "happiness.h"
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
#define mp make_pair

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf = 1e9;
const ll INF = 1e18;

struct Node {
	ll v;
	int l, r;

	Node() {
		v = 0;
		l = r = 0;
	}
};

ll n, m, sz, mx;
Node tree[20202020];

void update(int node, ll s, ll e, ll i, ll x) {
	if(s == e) {
		tree[node].v += x;
		return;
	}

	ll m = (s + e)/2;
	if(i <= m) {
		if(!tree[node].l) tree[node].l = ++sz;
		update(tree[node].l, s, m, i, x);
	}
	else {
		if(!tree[node].r) tree[node].r = ++sz;
		update(tree[node].r, m+1, e, i, x);
	}

	tree[node].v = tree[tree[node].l].v + tree[tree[node].r].v;
}

ll cal(int node, ll s, ll e, ll l, ll r) {
	if(r < s || e < l || !node) return 0;
	if(l <= s && e <= r) return tree[node].v;

	return cal(tree[node].l, s, (s+e)/2, l, r) + cal(tree[node].r, (s+e)/2+1, e, l, r);
}

bool chk() {
	ll sum = 0;
	while(sum < min(m, mx)) {
		ll x = cal(1, 0, m, 0, sum+1);
		if(x == sum) return false;

		sum = x;
	}

	return true;
}

bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
	n = coinsCount;
	m = maxCoinSize + 1;
	sz = 1;

	for(int i=0; i<n; i++) {
		update(1, 0, m, coins[i], coins[i]);
		mx += coins[i];
	}

	return chk();
}

bool is_happy(int event, int coinsCount, long long coins[]) {
	n = coinsCount;

	for(int i=0; i<n; i++) {
		update(1, 0, m, coins[i], event * coins[i]);
		mx += event * coins[i];
	}

	return chk();
}

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 184 ms 316664 KB Output is correct
2 Correct 195 ms 316664 KB Output is correct
3 Correct 183 ms 316560 KB Output is correct
4 Correct 184 ms 316536 KB Output is correct
5 Correct 183 ms 316664 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 316664 KB Output is correct
2 Correct 195 ms 316664 KB Output is correct
3 Correct 183 ms 316560 KB Output is correct
4 Correct 184 ms 316536 KB Output is correct
5 Correct 183 ms 316664 KB Output is correct
6 Correct 185 ms 316536 KB Output is correct
7 Correct 185 ms 316536 KB Output is correct
8 Correct 198 ms 316920 KB Output is correct
9 Correct 213 ms 316792 KB Output is correct
10 Correct 199 ms 316792 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 316664 KB Output is correct
2 Correct 195 ms 316664 KB Output is correct
3 Correct 183 ms 316560 KB Output is correct
4 Correct 184 ms 316536 KB Output is correct
5 Correct 183 ms 316664 KB Output is correct
6 Correct 582 ms 318024 KB Output is correct
7 Correct 556 ms 318072 KB Output is correct
8 Correct 609 ms 318072 KB Output is correct
9 Correct 740 ms 318200 KB Output is correct
10 Correct 810 ms 318176 KB Output is correct
11 Correct 363 ms 317304 KB Output is correct
12 Correct 407 ms 317204 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 316664 KB Output is correct
2 Correct 195 ms 316664 KB Output is correct
3 Correct 183 ms 316560 KB Output is correct
4 Correct 184 ms 316536 KB Output is correct
5 Correct 183 ms 316664 KB Output is correct
6 Correct 185 ms 316536 KB Output is correct
7 Correct 185 ms 316536 KB Output is correct
8 Correct 198 ms 316920 KB Output is correct
9 Correct 213 ms 316792 KB Output is correct
10 Correct 199 ms 316792 KB Output is correct
11 Correct 582 ms 318024 KB Output is correct
12 Correct 556 ms 318072 KB Output is correct
13 Correct 609 ms 318072 KB Output is correct
14 Correct 740 ms 318200 KB Output is correct
15 Correct 810 ms 318176 KB Output is correct
16 Correct 363 ms 317304 KB Output is correct
17 Correct 407 ms 317204 KB Output is correct
18 Correct 1082 ms 318444 KB Output is correct
19 Correct 1082 ms 317964 KB Output is correct
20 Correct 1366 ms 319396 KB Output is correct
21 Correct 806 ms 322580 KB Output is correct
22 Correct 449 ms 322680 KB Output is correct
23 Correct 468 ms 323048 KB Output is correct
24 Correct 1022 ms 323136 KB Output is correct