oj.uz

Submission #713507

# Submission time Handle Problem Language Result Execution time Memory
713507 2023-03-22T10:44:51 Z four_specks Happiness (Balkan15_HAPPINESS) C++17
100 / 100
 1588 ms 380200 KB 
#include "happiness.h"

#include <bits/stdc++.h>

using namespace std;

namespace
{
} // namespace

struct SegTree
{
    SegTree() {}
    SegTree(long _l, long _r) : l(_l), r(_r), val(0) {}

    long l, r;
    long val;

    unique_ptr<SegTree> lc, rc;

    void update(long p, long x)
    {
        val += x;

        if (r - l == 1)
            return;

        long mid = (l + r) / 2;

        if (p < mid)
        {
            if (!lc)
                lc = make_unique<SegTree>(l, mid);
            lc->update(p, x);
        }
        else
        {
            if (!rc)
                rc = make_unique<SegTree>(mid, r);
            rc->update(p, x);
        }
    }

    long query() const { return val; }

    long query(long pl, long pr) const
    {
        if (r <= pl || pr <= l)
            return 0;

        if (pl <= l && r <= pr)
            return val;

        long ret = 0;
        if (lc)
            ret += lc->query(pl, pr);
        if (rc)
            ret += rc->query(pl, pr);

        return ret;
    }
};

SegTree st;

bool check()
{
    long total = st.query();
    for (long sum = 1; sum < total;)
    {
        long cur = st.query(0, sum + 1);
        if (cur < sum)
            return 0;
        sum = cur + 1;
    }
    return 1;
}

bool init(int coinsCount, long long maxCoinSize, long long coins[])
{
    st = SegTree(0, maxCoinSize + 1);
    for (int i = 0; i < coinsCount; i++)
        st.update(coins[i], coins[i]);
    return check();
}

bool is_happy(int event, int coinsCount, long long coins[])
{
    for (int i = 0; i < coinsCount; i++)
        st.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 1 ms 212 KB Output is correct
2 Correct 1 ms 308 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 212 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 308 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 212 KB Output is correct
6 Correct 4 ms 1748 KB Output is correct
7 Correct 4 ms 2004 KB Output is correct
8 Correct 35 ms 14108 KB Output is correct
9 Correct 33 ms 14176 KB Output is correct
10 Correct 29 ms 13652 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 308 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 212 KB Output is correct
6 Correct 396 ms 37584 KB Output is correct
7 Correct 414 ms 37068 KB Output is correct
8 Correct 453 ms 37516 KB Output is correct
9 Correct 605 ms 48728 KB Output is correct
10 Correct 599 ms 52672 KB Output is correct
11 Correct 176 ms 36940 KB Output is correct
12 Correct 180 ms 37180 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 308 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 212 KB Output is correct
6 Correct 4 ms 1748 KB Output is correct
7 Correct 4 ms 2004 KB Output is correct
8 Correct 35 ms 14108 KB Output is correct
9 Correct 33 ms 14176 KB Output is correct
10 Correct 29 ms 13652 KB Output is correct
11 Correct 396 ms 37584 KB Output is correct
12 Correct 414 ms 37068 KB Output is correct
13 Correct 453 ms 37516 KB Output is correct
14 Correct 605 ms 48728 KB Output is correct
15 Correct 599 ms 52672 KB Output is correct
16 Correct 176 ms 36940 KB Output is correct
17 Correct 180 ms 37180 KB Output is correct
18 Correct 1119 ms 225908 KB Output is correct
19 Correct 1181 ms 234736 KB Output is correct
20 Correct 1588 ms 380200 KB Output is correct
21 Correct 808 ms 199184 KB Output is correct
22 Correct 203 ms 39112 KB Output is correct
23 Correct 210 ms 39548 KB Output is correct
24 Correct 970 ms 216728 KB Output is correct