oj.uz

Submission #836590

# Submission time Handle Problem Language Result Execution time Memory
836590 2023-08-24T13:11:29 Z mat_jur Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 1205 ms 524288 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, 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

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 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 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 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 4 ms 4544 KB Output is correct
7 Correct 5 ms 5332 KB Output is correct
8 Correct 42 ms 36048 KB Output is correct
9 Correct 42 ms 36272 KB Output is correct
10 Correct 40 ms 34664 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 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 664 ms 135584 KB Output is correct
7 Correct 704 ms 131292 KB Output is correct
8 Correct 774 ms 145784 KB Output is correct
9 Correct 969 ms 158632 KB Output is correct
10 Correct 994 ms 179024 KB Output is correct
11 Correct 253 ms 47972 KB Output is correct
12 Correct 262 ms 48084 KB Output is correct

Subtask #4
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 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 4 ms 4544 KB Output is correct
7 Correct 5 ms 5332 KB Output is correct
8 Correct 42 ms 36048 KB Output is correct
9 Correct 42 ms 36272 KB Output is correct
10 Correct 40 ms 34664 KB Output is correct
11 Correct 664 ms 135584 KB Output is correct
12 Correct 704 ms 131292 KB Output is correct
13 Correct 774 ms 145784 KB Output is correct
14 Correct 969 ms 158632 KB Output is correct
15 Correct 994 ms 179024 KB Output is correct
16 Correct 253 ms 47972 KB Output is correct
17 Correct 262 ms 48084 KB Output is correct
18 Runtime error 1205 ms 524288 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -