Submission #698588

#	Time	Username	Problem	Language	Result	Execution time	Memory
698588		finn__	Happiness (Balkan15_HAPPINESS)	C++17	100 / 100	996 ms	379532 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 = 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 (stderr)

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;
      |            ^~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40