Submission #698585

#	Time	Username	Problem	Language	Result	Execution time	Memory
698585		finn__	Happiness (Balkan15_HAPPINESS)	C++17	40 / 100	504 ms	70752 KiB

happiness

#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 (stderr)

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 / 10
• Subtask 2: 0 / 20
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40