제출 #836603

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
836603		mat_jur	Happiness (Balkan15_HAPPINESS)	C++17	100 / 100	1509 ms	483964 KiB

happiness

#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

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40