oj.uz

Submission #698585

# Submission time Handle Problem Language Result Execution time Memory
698585 2023-02-13T22:25:59 Z finn__ Happiness (Balkan15_HAPPINESS) C++17
40 / 100
 504 ms 70752 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, m;

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[])
{
    l = 1 << (32 - __builtin_clz(m));
    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:56:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   56 |     for (size_t i = 0; i < n; i++)
      |                        ~~^~~
happiness.cpp: In function 'bool is_happy(int, int, long long int*)':
happiness.cpp:63:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   63 |     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 300 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 300 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 300 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 305 ms 53516 KB Output is correct
7 Correct 284 ms 52852 KB Output is correct
8 Correct 303 ms 53576 KB Output is correct
9 Correct 496 ms 66484 KB Output is correct
10 Correct 504 ms 70752 KB Output is correct
11 Correct 156 ms 37024 KB Output is correct
12 Correct 153 ms 37120 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 300 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -