oj.uz

Submission #1091160

# Submission time Handle Problem Language Result Execution time Memory
1091160 2024-09-20T01:20:47 Z anmattroi Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 1628 ms 524288 KB 
#include "happiness.h"
#include <bits/stdc++.h>

using namespace std;

struct vertex {
    vertex *left_child = nullptr, *right_child = nullptr;
    int64_t lz = 0;
    int64_t val = 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 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;
    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 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 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 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 5 ms 3420 KB Output is correct
7 Correct 5 ms 3676 KB Output is correct
8 Correct 51 ms 27472 KB Output is correct
9 Correct 49 ms 27540 KB Output is correct
10 Correct 48 ms 26704 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 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 621 ms 65008 KB Output is correct
7 Correct 596 ms 64140 KB Output is correct
8 Correct 608 ms 64952 KB Output is correct
9 Correct 986 ms 83288 KB Output is correct
10 Correct 1055 ms 90016 KB Output is correct
11 Correct 284 ms 58964 KB Output is correct
12 Correct 306 ms 59224 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 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 5 ms 3420 KB Output is correct
7 Correct 5 ms 3676 KB Output is correct
8 Correct 51 ms 27472 KB Output is correct
9 Correct 49 ms 27540 KB Output is correct
10 Correct 48 ms 26704 KB Output is correct
11 Correct 621 ms 65008 KB Output is correct
12 Correct 596 ms 64140 KB Output is correct
13 Correct 608 ms 64952 KB Output is correct
14 Correct 986 ms 83288 KB Output is correct
15 Correct 1055 ms 90016 KB Output is correct
16 Correct 284 ms 58964 KB Output is correct
17 Correct 306 ms 59224 KB Output is correct
18 Correct 1452 ms 438728 KB Output is correct
19 Correct 1628 ms 456076 KB Output is correct
20 Runtime error 1299 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -