oj.uz

Submission #641774

# Submission time Handle Problem Language Result Execution time Memory
641774 2022-09-17T15:11:04 Z finn__ Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 1495 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;

#include "happiness.h"

struct tnode
{
    int64_t t;
    tnode *l, *r;
    uint64_t x, y;

    void new_node()
    {

        if (!l)
        {
            l = new tnode;
            l->l = 0;
            l->r = 0;
            l->t = 0;
            l->x = x;
            l->y = (x + y) / 2;
        }

        if (!r)
        {
            r = new tnode;
            r->l = 0;
            r->r = 0;
            r->t = 0;
            r->x = (x + y) / 2 + 1;
            r->y = y;
        }
    }

    void update(uint64_t i, int64_t v)
    {
        if (x == i && y == i)
            t += v;
        else
        {
            new_node();

            if (i <= (x + y) / 2)
                l->update(i, v);
            else
                r->update(i, v);

            t = l->t + r->t;
        }
    }

    int64_t range_sum(uint64_t i, uint64_t j)
    {
        if (y < i || x > j)
            return 0;
        if (i <= x && y <= j)
            return t;
        else
        {
            new_node();
            return l->range_sum(i, j) + r->range_sum(i, j);
        }
    }
};

tnode *root;

bool check()
{
    int64_t curr = 1, sum = root->t;
    while (curr < sum)
    {
        int64_t v = root->range_sum(1, curr);
        if (v < curr)
            return 0;
        curr = v + 1;
    }
    return 1;
}

bool init(int coinsCount, long long maxCoinSize, long long coins[])
{
    root = new tnode;
    root->t = 0;
    root->x = 0;
    root->y = maxCoinSize + 1;
    root->l = 0;
    root->r = 0;
    for (int i = 0; i < coinsCount; i++)
        root->update(coins[i], coins[i]);
    return check();
}
bool is_happy(int event, int coinsCount, long long coins[])
{
    for (int i = 0; i < coinsCount; i++)
        root->update(coins[i], event * coins[i]);
    return check();
}

Compilation message

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 1 ms 268 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 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 1 ms 268 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 5 ms 3540 KB Output is correct
7 Correct 5 ms 4052 KB Output is correct
8 Correct 45 ms 27156 KB Output is correct
9 Correct 45 ms 27340 KB Output is correct
10 Correct 41 ms 26188 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 1 ms 268 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 495 ms 54216 KB Output is correct
7 Correct 480 ms 54140 KB Output is correct
8 Correct 514 ms 54296 KB Output is correct
9 Correct 665 ms 66808 KB Output is correct
10 Correct 670 ms 71040 KB Output is correct
11 Correct 186 ms 36976 KB Output is correct
12 Correct 164 ms 37108 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 1 ms 268 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 5 ms 3540 KB Output is correct
7 Correct 5 ms 4052 KB Output is correct
8 Correct 45 ms 27156 KB Output is correct
9 Correct 45 ms 27340 KB Output is correct
10 Correct 41 ms 26188 KB Output is correct
11 Correct 495 ms 54216 KB Output is correct
12 Correct 480 ms 54140 KB Output is correct
13 Correct 514 ms 54296 KB Output is correct
14 Correct 665 ms 66808 KB Output is correct
15 Correct 670 ms 71040 KB Output is correct
16 Correct 186 ms 36976 KB Output is correct
17 Correct 164 ms 37108 KB Output is correct
18 Correct 1472 ms 447268 KB Output is correct
19 Correct 1495 ms 457360 KB Output is correct
20 Runtime error 1311 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -