Submission #1091171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091171		anmattroi	Happiness (Balkan15_HAPPINESS)	C++14	100 / 100	1974 ms	435028 KiB

happiness

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

using namespace std;

struct vertex {
    vertex *left_child = nullptr, *right_child = nullptr;
    int64_t sum = 0, minprefix = 0;
    bool L = 0, R = 0;

    vertex() {}
    ~vertex() {
        delete left_child;
        delete right_child;
        left_child = nullptr;
        right_child = nullptr;
    }

    void extend() {
        if (left_child == nullptr) left_child = new vertex;
        if (right_child == nullptr) right_child = new vertex;
    }
    void extend_left() {
        if (!L) {left_child = new vertex; L = 1;}

    }
    void extend_right() {
        if (!R) {right_child = new vertex; R = 1;}
    }

    void Lup() {
        sum = left_child->sum + (R ? right_child->sum : 0);
        minprefix = min(left_child->minprefix, left_child->sum + (R ? right_child->minprefix : 0));
    }
    void Rup() {
        sum = (L ? left_child->sum : 0) + right_child->sum;
        minprefix = min((L ? left_child->minprefix : 0), (L ? left_child->sum : 0) + right_child->minprefix);
    }
};

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

void upd(int64_t u, int64_t d, vertex *cur = &root, int64_t lo = 1, int64_t hi = MAXC) {
    if (lo == hi) {
        cur->sum += d;
        cur->minprefix = cur->sum;
        return;
    }
    int64_t mid = (lo + hi) >> 1LL;
    if (u <= mid) {
        cur->extend_left();
        upd(u, d, cur->left_child, lo, mid);
        cur->Lup();
    } else {
        cur->extend_right();
        upd(u, d, cur->right_child, mid + 1, hi);
        cur->Rup();
    }
}


bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
    MAXC = maxCoinSize;
    for (int i = 0; i < coinsCount; i++) {
        int64_t val = coins[i];
        if (!nho.count(val)) {
            upd(val, -val);
            if (val < MAXC) upd(val+1, val);
        }
        ++nho[val];
    }
    for (int i = 0; i < coinsCount; i++) {
        int64_t val = coins[i];
        if (val < MAXC) upd(val+1, val);
    }
    return (root.minprefix >= -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);
                if (val < MAXC) upd(val+1, val);
            } else if (nho[val] == 0) {
                upd(val, -val);
                if (val < MAXC) upd(val+1, val);
            }
            ++nho[val];
        } else {
            --nho[val];
            if (nho[val] == 0) {
                upd(val, val);
                if (val < MAXC) upd(val+1, -val);
            }
        }
        if (val < MAXC) upd(val+1, event * val);
    }
    return (root.minprefix >= -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: 40 / 40