oj.uz

Submission #1091159

# Submission time Handle Problem Language Result Execution time Memory
1091159 2024-09-20T01:15:56 Z anmattroi Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 1386 ms 524288 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, 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

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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 5 ms 4444 KB Output is correct
7 Correct 9 ms 4808 KB Output is correct
8 Correct 61 ms 36240 KB Output is correct
9 Correct 56 ms 36432 KB Output is correct
10 Correct 53 ms 35240 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 680 ms 81476 KB Output is correct
7 Correct 662 ms 80476 KB Output is correct
8 Correct 690 ms 81492 KB Output is correct
9 Correct 1079 ms 103616 KB Output is correct
10 Correct 1079 ms 111948 KB Output is correct
11 Correct 293 ms 69968 KB Output is correct
12 Correct 311 ms 69996 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 5 ms 4444 KB Output is correct
7 Correct 9 ms 4808 KB Output is correct
8 Correct 61 ms 36240 KB Output is correct
9 Correct 56 ms 36432 KB Output is correct
10 Correct 53 ms 35240 KB Output is correct
11 Correct 680 ms 81476 KB Output is correct
12 Correct 662 ms 80476 KB Output is correct
13 Correct 690 ms 81492 KB Output is correct
14 Correct 1079 ms 103616 KB Output is correct
15 Correct 1079 ms 111948 KB Output is correct
16 Correct 293 ms 69968 KB Output is correct
17 Correct 311 ms 69996 KB Output is correct
18 Runtime error 1386 ms 524288 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -