Submission #1127989

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127989		mnbvcxz123	Happiness (Balkan15_HAPPINESS)	C++20	100 / 100	1298 ms	372248 KiB

happiness

#include "happiness.h"

struct Node {
    long long l, r, val;
    Node *lc, *rc;

    Node(long long L, long long R): l(L), r(R), val(0), lc(nullptr), rc(nullptr) {}

    void update(long long p, long long v) {
        val += v;
        if (l != r) {
            long long mid = (l + r) / 2;
            if (p > mid) {
                if (!rc) rc = new Node(mid + 1, r);
                rc->update(p, v);
            } else {
                if (!lc) lc = new Node(l, mid);
                lc->update(p, v);    
            }
        }
    }

    long long query(long long a, long long b) {
        if (r < a || l > b) return 0;
        if (r <= b && l >= a) return val;
        long long ret = 0;
        if (lc) ret += lc->query(a, b);
        if (rc) ret += rc->query(a, b);
        return ret;
    }
};

Node *root;

bool check() {
    long long curr = 1, sm = root->val;
    while (curr < sm) {
        long long t = root->query(1, curr);
        if (t < curr) return false;
        curr = t + 1;
    }
    return true;
}

bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
    root = new Node(1, maxCoinSize);
    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();
}

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