oj.uz

Submission #698587

# Submission time Handle Problem Language Result Execution time Memory
698587 2023-02-13T22:34:47 Z finn__ Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 949 ms 524288 KB 
#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;

void check_children(Node *const x)
{
    if (!x->left)
    {
        x->left = (Node *)calloc(1, sizeof *x->left);
        x->left->min_prefix_sum = INT64_MAX / 2;
    }
    if (!x->right)
    {
        x->right = (Node *)calloc(1, sizeof *x->right);
        x->right->min_prefix_sum = INT64_MAX / 2;
    }
}

void combine(Node *const x)
{
    x->sum = x->left->sum + x->right->sum;
    x->min_prefix_sum = min(x->left->min_prefix_sum,
                            x->left->sum + x->right->min_prefix_sum);
}

void update(int64_t i, Node *const x, int64_t a, int64_t b, int64_t t)
{
    if (a + 1 == b)
    {
        x->sum += t * i;
        x->min_prefix_sum = x->sum ? -i + 1 : INT64_MAX / 2;
        return;
    }
    check_children(x);
    if (i <= (a + b) >> 1)
        update(i, x->left, a, (a + b) >> 1, t);
    else
        update(i, x->right, (a + b) >> 1, b, t);
    combine(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:57:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   57 |     for (size_t i = 0; i < n; i++)
      |                        ~~^~~
happiness.cpp: In function 'bool is_happy(int, int, long long int*)':
happiness.cpp:64:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   64 |     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;
      |            ^~~~~~~~

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 256 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 256 KB Output is correct
6 Correct 3 ms 3156 KB Output is correct
7 Correct 6 ms 3540 KB Output is correct
8 Correct 34 ms 26660 KB Output is correct
9 Correct 34 ms 26792 KB Output is correct
10 Correct 33 ms 25932 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 256 KB Output is correct
6 Correct 305 ms 50268 KB Output is correct
7 Correct 333 ms 49752 KB Output is correct
8 Correct 306 ms 50356 KB Output is correct
9 Correct 511 ms 61956 KB Output is correct
10 Correct 510 ms 66284 KB Output is correct
11 Correct 153 ms 33228 KB Output is correct
12 Correct 196 ms 33356 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 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 3 ms 3156 KB Output is correct
7 Correct 6 ms 3540 KB Output is correct
8 Correct 34 ms 26660 KB Output is correct
9 Correct 34 ms 26792 KB Output is correct
10 Correct 33 ms 25932 KB Output is correct
11 Correct 305 ms 50268 KB Output is correct
12 Correct 333 ms 49752 KB Output is correct
13 Correct 306 ms 50356 KB Output is correct
14 Correct 511 ms 61956 KB Output is correct
15 Correct 510 ms 66284 KB Output is correct
16 Correct 153 ms 33228 KB Output is correct
17 Correct 196 ms 33356 KB Output is correct
18 Correct 839 ms 425332 KB Output is correct
19 Correct 847 ms 442168 KB Output is correct
20 Runtime error 949 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -