Submission #1188683

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188683		sonya	Happiness (Balkan15_HAPPINESS)	C++20	10 / 100	2094 ms	11432 KiB

happiness

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

struct Node {
    int left = 0, right = 0;
    long long count = 0;
};

const long long MAX_VAL = 1e12;
vector<Node> tree(2);
int next_id = 2;

void update(int node, long long l, long long r, long long pos, int diff) {
    if (l == r) {
        tree[node].count += diff;
        return;
    }
    long long mid = (l + r) / 2;
    if (pos <= mid) {
        if (!tree[node].left) {
            tree[node].left = next_id++;
            if (tree.size() <= next_id) tree.resize(next_id + 5);
        }
        update(tree[node].left, l, mid, pos, diff);
    } else {
        if (!tree[node].right) {
            tree[node].right = next_id++;
            if (tree.size() <= next_id) tree.resize(next_id + 5);
        }
        update(tree[node].right, mid + 1, r, pos, diff);
    }

    tree[node].count = 0;
    if (tree[node].left) tree[node].count += tree[tree[node].left].count;
    if (tree[node].right) tree[node].count += tree[tree[node].right].count;
}

bool dfs_check(int node, long long l, long long r, long long &reach) {
    if (!node) return true;
    if (l == r) {
        if (l > reach + 1 && tree[node].count > 0)
            return false;
        reach += tree[node].count * l;
        if (reach >= 1e18) reach = 1e18;
        return true;
    }
    long long mid = (l + r) / 2;

    if (!dfs_check(tree[node].left, l, mid, reach)) return false;
    if (!dfs_check(tree[node].right, mid + 1, r, reach)) return false;
    return true;
}

bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
    tree = vector<Node>(2);
    next_id = 2;
    for (int i = 0; i < coinsCount; ++i)
        update(1, 1, MAX_VAL, coins[i], 1);

    long long reach = 0;
    return dfs_check(1, 1, MAX_VAL, reach);
}

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

    long long reach = 0;
    return dfs_check(1, 1, MAX_VAL, reach);
}

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