Submission #1188675

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188675		sonya	Happiness (Balkan15_HAPPINESS)	C++20	0 / 100	0 ms	320 KiB

happiness

#include "happiness.h"
#include <map>
using namespace std;

struct Node {
    Node* left = nullptr;
    Node* right = nullptr;
    long long sum = 0, count = 0;
};

Node* root = new Node();
const long long MAX = 1e12;

void update(Node*& node, long long l, long long r, long long pos, long long val, long long delta) {
    if (!node) node = new Node();

    node->sum += val;
    node->count += delta;

    if (l == r) return;

    long long mid = (l + r) / 2;
    if (pos <= mid) update(node->left, l, mid, pos, val, delta);
    else update(node->right, mid + 1, r, pos, val, delta);
}

pair<long long, long long> query(Node* node, long long l, long long r, long long ql, long long qr) {
    if (!node || l > qr || r < ql) return {0, 0};
    if (ql <= l && r <= qr) return {node->sum, node->count};

    long long mid = (l + r) / 2;
    auto left = query(node->left, l, mid, ql, qr);
    auto right = query(node->right, mid + 1, r, ql, qr);
    return {left.first + right.first, left.second + right.second};
}

bool is_happy_now() {
    long long reach = 0;
    long long next = 1;

    while (true) {
        auto [s, c] = query(root, 1, MAX, next, reach + 1);
        if (c == 0) break;

        reach += s;
        next = reach + 1;
        if (reach > 1e18) break;
    }

    auto [total, _] = query(root, 1, MAX, 1, MAX);
    return reach >= total;
}

bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
    root = new Node();
    for (int i = 0; i < coinsCount; ++i) {
        update(root, 1, MAX, coins[i], coins[i], 1);
    }
    return is_happy_now();
}

bool is_happy(int event, int coinsCount, long long coins[]) {
    if (event == -1) {
        for (int i = 0; i < coinsCount; ++i)
            update(root, 1, MAX, coins[i], -coins[i], -1);
    } else {
        for (int i = 0; i < coinsCount; ++i)
            update(root, 1, MAX, coins[i], coins[i], 1);
    }
    return is_happy_now();
}

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