#include <bits/stdc++.h>
#include "happiness.h"
using namespace std;
struct Node
{
Node *left, *right;
int64_t sum, min_prefix_sum;
};
Node *root;
int64_t l = 1;
Node *update(int64_t i, Node *x, int64_t a, int64_t b, int64_t t)
{
if (!x)
{
x = (Node *)calloc(1, sizeof *x);
x->min_prefix_sum = INT64_MAX / 2;
}
if (a + 1 == b)
{
x->sum += t * i;
x->min_prefix_sum = x->sum ? -i + 1 : INT64_MAX / 2;
return x;
}
if (i <= (a + b) >> 1)
{
x->left = update(i, x->left, a, (a + b) >> 1, t);
x->sum = x->left->sum + (x->right ? x->right->sum : 0);
x->min_prefix_sum = x->left->min_prefix_sum;
if (x->right)
x->min_prefix_sum = min(x->min_prefix_sum, x->left->sum + x->right->min_prefix_sum);
}
else
{
x->right = update(i, x->right, (a + b) >> 1, b, t);
x->sum = (x->left ? x->left->sum : 0) + x->right->sum;
if (x->left)
x->min_prefix_sum = min(x->left->min_prefix_sum, x->left->sum + x->right->min_prefix_sum);
else
x->min_prefix_sum = x->right->min_prefix_sum;
}
return x;
}
bool init(int n, long long m, long long coins[])
{
while (l < m)
l <<= 1;
root = (Node *)calloc(1, sizeof *root);
for (size_t i = 0; i < n; i++)
update(coins[i], root, 0, l, 1);
return root->min_prefix_sum >= 0;
}
bool is_happy(int event, int n, long long coins[])
{
for (size_t i = 0; i < n; i++)
update(coins[i], root, 0, l, event);
return root->min_prefix_sum >= 0;
}
Compilation message
happiness.cpp: In function 'bool init(int, long long int, long long int*)':
happiness.cpp:54:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
54 | for (size_t i = 0; i < n; i++)
| ~~^~~
happiness.cpp: In function 'bool is_happy(int, int, long long int*)':
happiness.cpp:61:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
61 | for (size_t i = 0; i < n; i++)
| ~~^~~
grader.cpp: In function 'int main()':
grader.cpp:16:12: warning: unused variable 'max_code' [-Wunused-variable]
16 | long long max_code;
| ^~~~~~~~
# |
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 |
0 ms |
212 KB |
Output is correct |
# |
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 |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
2 ms |
1748 KB |
Output is correct |
7 |
Correct |
4 ms |
1944 KB |
Output is correct |
8 |
Correct |
22 ms |
13852 KB |
Output is correct |
9 |
Correct |
22 ms |
14036 KB |
Output is correct |
10 |
Correct |
20 ms |
13556 KB |
Output is correct |
# |
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 |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
267 ms |
34252 KB |
Output is correct |
7 |
Correct |
264 ms |
33820 KB |
Output is correct |
8 |
Correct |
255 ms |
34256 KB |
Output is correct |
9 |
Correct |
441 ms |
44084 KB |
Output is correct |
10 |
Correct |
442 ms |
47972 KB |
Output is correct |
11 |
Correct |
150 ms |
33268 KB |
Output is correct |
12 |
Correct |
157 ms |
33224 KB |
Output is correct |
# |
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 |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
2 ms |
1748 KB |
Output is correct |
7 |
Correct |
4 ms |
1944 KB |
Output is correct |
8 |
Correct |
22 ms |
13852 KB |
Output is correct |
9 |
Correct |
22 ms |
14036 KB |
Output is correct |
10 |
Correct |
20 ms |
13556 KB |
Output is correct |
11 |
Correct |
267 ms |
34252 KB |
Output is correct |
12 |
Correct |
264 ms |
33820 KB |
Output is correct |
13 |
Correct |
255 ms |
34256 KB |
Output is correct |
14 |
Correct |
441 ms |
44084 KB |
Output is correct |
15 |
Correct |
442 ms |
47972 KB |
Output is correct |
16 |
Correct |
150 ms |
33268 KB |
Output is correct |
17 |
Correct |
157 ms |
33224 KB |
Output is correct |
18 |
Correct |
611 ms |
220016 KB |
Output is correct |
19 |
Correct |
615 ms |
228760 KB |
Output is correct |
20 |
Correct |
996 ms |
379532 KB |
Output is correct |
21 |
Correct |
536 ms |
198764 KB |
Output is correct |
22 |
Correct |
238 ms |
39056 KB |
Output is correct |
23 |
Correct |
237 ms |
39604 KB |
Output is correct |
24 |
Correct |
561 ms |
216380 KB |
Output is correct |