Submission #1091154

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091154		anmattroi	Happiness (Balkan15_HAPPINESS)	C++14	0 / 100	0 ms	348 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;

void update(int64_t u, int64_t v, int 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];
        upd(val, -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 (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: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40