oj.uz

Submission #1091158

# Submission time Handle Problem Language Result Execution time Memory
1091158 2024-09-20T01:13:29 Z anmattroi Happiness (Balkan15_HAPPINESS) C++14
40 / 100
 1144 ms 111984 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;
map<int64_t, int> 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[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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 504 KB Output is correct
3 Correct 0 ms 440 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 504 KB Output is correct
3 Correct 0 ms 440 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 5 ms 4444 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 504 KB Output is correct
3 Correct 0 ms 440 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 724 ms 81456 KB Output is correct
7 Correct 697 ms 80584 KB Output is correct
8 Correct 667 ms 81308 KB Output is correct
9 Correct 1075 ms 103768 KB Output is correct
10 Correct 1144 ms 111984 KB Output is correct
11 Correct 336 ms 70036 KB Output is correct
12 Correct 326 ms 70048 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 504 KB Output is correct
3 Correct 0 ms 440 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 5 ms 4444 KB Output isn't correct
7 Halted 0 ms 0 KB -