oj.uz

Submission #836603

# Submission time Handle Problem Language Result Execution time Memory
836603 2023-08-24T13:16:24 Z mat_jur Happiness (Balkan15_HAPPINESS) C++17
100 / 100
 1509 ms 483964 KB 
#include <bits/stdc++.h>
using namespace std;
#ifndef LOCAL
#include <happiness.h>
#endif
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto &o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else 
#define debug(X) ;
#endif
#define ll long long
#define all(v) (v).begin(), (v).end()
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
#define fi first
#define se second

struct Node {
	ll val;
	Node *left, *right;
	Node() {
		val = 0;
		left = right = nullptr;
	}
};
Node root;

void push_to_sons(Node &v) {
	if (v.left == nullptr) {
		v.left = new Node();
		v.right = new Node();
	}
}

void update(ll a, ll x, Node &v, ll l = 0, ll r = ((ll)1<<40)-1) {
//	cerr << l << ' ' << r << '\n';
	if (r < a || a < l) return; 
	if (l == r) {
		v.val += x;
		return;
	}
	push_to_sons(v);
	ll mid = (l+r)/2;
	update(a, x, *v.left, l, mid); update(a, x, *v.right, mid+1, r);
	v.val = (v.left)->val+(v.right)->val;
}

ll query(ll a, ll b, Node &v, ll l = 0, ll r = ((ll)1<<40)-1) {
	if (r < a || b < l) return 0;
	if (a <= l && r <= b) return v.val;
	push_to_sons(v);
	ll mid = (l+r)/2;
	return query(a, b, *v.left, l, mid) + query(a, b, *v.right, mid+1, r);
}

bool check() {
	ll curr = 1, sum = root.val;
	while (curr < sum) {
		ll t = query(0, curr, root);
		if (t < curr) return false;
		curr = t+1;
	}
	return true;
}

bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
	REP(i, coinsCount) {
		update(coins[i], coins[i], root);
	}
	return check();
}

bool is_happy(int event, int coinsCount, long long coins[]) {
	REP(i, coinsCount) {
		update(coins[i], (ll)event*coins[i], root);
	}
	return check();
}

void clean(Node v) {
	if (v.left == nullptr) return;
	clean(*v.left); clean(*v.right);
	delete v.left; delete v.right;
}

#ifdef LOCAL
int main () {
	ll a1[] = {4, 8, 1, 2, 16};
	ll a2[] = {2, 8};
	ll a3[] = {7, 9, 2};
	cout << init(5, 100, a1) << '\n';
	cout << is_happy(-1, 2, a2) << '\n';
	cout << is_happy(1, 3, a3) << '\n';
	clean(root);
}
#endif

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 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 2388 KB Output is correct
7 Correct 4 ms 2772 KB Output is correct
8 Correct 31 ms 18024 KB Output is correct
9 Correct 31 ms 18236 KB Output is correct
10 Correct 29 ms 17388 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 536 ms 66860 KB Output is correct
7 Correct 549 ms 64692 KB Output is correct
8 Correct 649 ms 71936 KB Output is correct
9 Correct 700 ms 77692 KB Output is correct
10 Correct 707 ms 87916 KB Output is correct
11 Correct 227 ms 22332 KB Output is correct
12 Correct 219 ms 22380 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 2388 KB Output is correct
7 Correct 4 ms 2772 KB Output is correct
8 Correct 31 ms 18024 KB Output is correct
9 Correct 31 ms 18236 KB Output is correct
10 Correct 29 ms 17388 KB Output is correct
11 Correct 536 ms 66860 KB Output is correct
12 Correct 549 ms 64692 KB Output is correct
13 Correct 649 ms 71936 KB Output is correct
14 Correct 700 ms 77692 KB Output is correct
15 Correct 707 ms 87916 KB Output is correct
16 Correct 227 ms 22332 KB Output is correct
17 Correct 219 ms 22380 KB Output is correct
18 Correct 1065 ms 300180 KB Output is correct
19 Correct 1132 ms 306652 KB Output is correct
20 Correct 1509 ms 483964 KB Output is correct
21 Correct 888 ms 282188 KB Output is correct
22 Correct 281 ms 28108 KB Output is correct
23 Correct 276 ms 28640 KB Output is correct
24 Correct 1064 ms 312528 KB Output is correct