oj.uz

Submission #1091157

# Submission time Handle Problem Language Result Execution time Memory
1091157 2024-09-20T01:10:32 Z anmattroi Happiness (Balkan15_HAPPINESS) C++14
0 / 100
 0 ms 344 KB 
#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;
set<int64_t> nho;

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];
        if (!nho.count(val)) {
            upd(val, -val);
            nho.insert(val);
        }
        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 (!nho.count(val)) {
            upd(val, -val);
            nho.insert(val);
        }
        if (val < MAXC) update(val+1, MAXC, event * val);
    }
    return (root.val >= -1);
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -