제출 #836590

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
836590		mat_jur	Happiness (Balkan15_HAPPINESS)	C++17	60 / 100	1205 ms	524288 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, lazy;
	ll start, end;
	Node *left, *right;
	Node() {
		val = lazy = 0;
		start = 0; end = (ll)((ll)1<<40)-1;
		left = right = nullptr;
	}
	Node(ll l, ll r) {
		val = lazy = 0;
		start = l, end = r;
		left = right = nullptr;
	}	
};
Node root;

void push_to_sons(Node &v) {
	ll x = v.lazy;
	if (v.left == nullptr) {
		ll mid = (v.start+v.end)/2;
		v.left = new Node(v.start, mid);
		v.right = new Node(mid+1, v.end);
	}
	if (x == 0) return;
	(v.left)->val += x;
	(v.right)->val += x;
	(v.left)->lazy += x;
	(v.right)->lazy += x;
	v.lazy = 0;
}

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

ll query(ll a, ll b, Node &v) {
	ll l = v.start, r = v.end;
	if (r < a || b < l) return 0;
	if (a <= l && r <= b) return v.val;
	push_to_sons(v);
	return query(a, b, *v.left) + query(a, b, *v.right);
}

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: 0 / 40