Submission #1091159

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091159		anmattroi	Happiness (Balkan15_HAPPINESS)	C++14	60 / 100	1386 ms	524288 KiB

happiness

#include "happiness.h"
#include <bits/stdc++.h>

using namespace std;

struct vertex {
    vertex *left_child = nullptr, *right_child = nullptr;
    int64_t lo, hi, lz = 0;
    int64_t val = 0;

    vertex() {}
    vertex(int64_t l, int64_t r) : lo(l), hi(r) {}
    ~vertex() {
        delete left_child;
        delete right_child;
        left_child = nullptr;
        right_child = nullptr;
    }

    void extend() {
        int64_t mid = (lo + hi) >> 1LL;
        if (left_child == nullptr) left_child = new vertex(lo, mid);
        if (right_child == nullptr) right_child = new vertex(mid + 1, hi);
    }

    void down() {
        if (lz == 0) return;
        left_child->val += lz;
        right_child->val += lz;
        left_child->lz += lz;
        right_child->lz += lz;
        lz = 0;
    }

    void up() {
        val = min(left_child->val, right_child->val);
    }
};

vertex root;
int64_t MAXC;
map<int64_t, int> nho;

void update(int64_t u, int64_t v, int64_t d, vertex *cur = &root, int64_t lo = 1, int64_t hi = MAXC) {
    if (u > hi || v < lo) return;
    if (u <= lo && hi <= v) {
        cur->val += d;
        cur->lz += d;
        return;
    }
    cur->extend();
    cur->down();
    int64_t mid = (lo + hi) >> 1LL;
    update(u, v, d, cur->left_child, lo, mid);
    update(u, v, d, cur->right_child, mid+1, hi);
    cur->up();
}
void upd(int64_t u, int64_t d, vertex *cur = &root, int64_t lo = 1, int64_t hi = MAXC) {
    if (lo == hi) {
        cur->val += d;
        return;
    }
    cur->extend();
    cur->down();
    int64_t mid = (lo + hi) >> 1LL;
    if (u <= mid) upd(u, d, cur->left_child, lo, mid);
    else upd(u, d, cur->right_child, mid + 1, hi);
    cur->up();
}


bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
    MAXC = maxCoinSize;
    root = vertex(1, MAXC);
    for (int i = 0; i < coinsCount; i++) {
        int64_t val = coins[i];
        if (!nho.count(val)) upd(val, -val);
        ++nho[val];
    }
    for (int i = 0; i < coinsCount; i++) {
        int64_t val = coins[i];
        if (val < MAXC) update(val+1, MAXC, val);
    }
    return (root.val >= -1);
}

bool is_happy(int event, int coinsCount, long long coins[]) {
    for (int i = 0; i < coinsCount; i++) {
        int64_t val = coins[i];
        if (event == 1) {
            if (!nho.count(val)) {
                upd(val, -val);
            } else if (nho[val] == 0) {
                upd(val, -val);
            }
            ++nho[val];
        } else {
            --nho[val];
            if (nho[val] == 0) upd(val, val);
        }
        if (val < MAXC) update(val+1, MAXC, event * val);
    }
    return (root.val >= -1);
}

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: 0 / 40