Submission #713507

#	Time	Username	Problem	Language	Result	Execution time	Memory
713507		four_specks	Happiness (Balkan15_HAPPINESS)	C++17	100 / 100	1588 ms	380200 KiB

happiness

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

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