Submission #704132

#	Time	Username	Problem	Language	Result	Execution time	Memory
704132		mihai145	Happiness (Balkan15_HAPPINESS)	C++17	100 / 100	1150 ms	443820 KiB

happiness

// Test problem: https://oj.uz/problem/view/Balkan15_HAPPINESS
// Reusing vertices

#include <vector>
#include "happiness.h"

using namespace std;

const int LOG = 20; // should be ~40
const int MAX_N = 200000;
const int SZ = 4 * MAX_N * LOG;

class DynamicSegmentTree {
private:
    struct State {
        long long range_sum, range_min_ok;
    };
    State v[SZ];
    pair<int, int> sons[SZ];

    vector<int> available;

    // messy tricks to reduce memory
    long long encode(long long val, bool ok) {
        return val * 10 + ok;
    }

    pair<long long, bool> decode(long long val) {
        return {val / 10, (val % 10 == 1)};
    }

    void clear(int idx) {
        v[idx].range_sum = 0;
        v[idx].range_min_ok = encode(0, true);
        sons[idx].first = sons[idx].second = -1;
    }

    void init(int idx) {
        if (sons[idx].first == -1) {
            sons[idx].first = available.back(), available.pop_back();
        }
        if (sons[idx].second == -1) {
            sons[idx].second = available.back(), available.pop_back();
        }
    }

    State merge(const State &a, const State &b) {
        State res;
        res.range_sum = a.range_sum + b.range_sum;
        pair<long long, bool> ark = decode(a.range_min_ok), brk = decode(b.range_min_ok);

        long long range_min;
        if (min(ark.first, brk.first) > 0) {
            range_min = min(ark.first, brk.first);
        } else {
            range_min = max(ark.first, brk.first);
        }
        bool ok = ark.second && (1 + a.range_sum >= brk.first);

        res.range_min_ok = encode(range_min, ok);
        return res;
    }

public:
    void Init() {
        for (int i = SZ - 1; i >= 1; i--) {
            available.push_back(i);
            clear(i);
        }
        available.pop_back();
    }

    void Update(int idx, long long l, long long r, long long pos, int sgn, int par = -1) {
        if (sons[idx].first == -1 || sons[idx].second == -1) {
            init(idx);
        }

        if (l == r) {
            v[idx].range_sum += sgn * pos;
            v[idx].range_min_ok = encode(((v[idx].range_sum > 0) ? pos : 0), true);

            if (v[idx].range_sum == 0) {
                if (par == -1) return;
                if (sons[par].first == idx) { sons[par].first = -1; }
                else { sons[par].second = -1; }
                clear(idx);
                available.push_back(idx);
            }
            return;
        }

        long long mid = (l + r) >> 1;
        if (pos <= mid) Update(sons[idx].first, l, mid, pos, sgn, idx);
        else Update(sons[idx].second, mid + 1, r, pos, sgn, idx);

        if (sons[idx].first == -1) {
            v[idx] = (sons[idx].second != -1 ? v[sons[idx].second] : State{0, encode(0, true)});
        } else {
            v[idx] = merge(v[sons[idx].first],
                           (sons[idx].second != -1 ? v[sons[idx].second] : State{0, encode(0, true)}));
        }
    }

    bool GetValid() {
        return decode(v[1].range_min_ok).second;
    }
};

DynamicSegmentTree dst;

int nr_coins, fv_1;
long long max_coin_size;

bool get_is_happy() {
    return (nr_coins == 0) || (fv_1 >= 1 && dst.GetValid());
}

bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
    dst.Init();
    nr_coins = coinsCount;
    max_coin_size = maxCoinSize;

    for (int i = 0; i < coinsCount; i++) {
        dst.Update(1, 1, max_coin_size, coins[i], 1);
        if (coins[i] == 1) fv_1++;
    }

    return get_is_happy();
}

bool is_happy(int event, int coinsCount, long long coins[]) {
    nr_coins += event * coinsCount;
    for (int i = 0; i < coinsCount; i++) {
        dst.Update(1, 1, max_coin_size, coins[i], event);
        if (coins[i] == 1) fv_1 += event;
    }

    return get_is_happy();
}

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