oj.uz

Submission #1091162

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

using namespace std;

struct vertex {
    vertex *left_child = nullptr, *right_child = nullptr;
    int64_t sum = 0, minprefix = 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 up() {
        sum = left_child->sum + right_child->sum;
        minprefix = min(left_child->minprefix, left_child->sum + right_child->minprefix);
    }
};

vertex root;
int64_t MAXC;
map<int64_t, int> nho;

void upd(int64_t u, int64_t d, vertex *cur = &root, int64_t lo = 1, int64_t hi = MAXC) {
    if (lo == hi) {
        cur->sum += d;
        cur->minprefix = cur->sum;
        return;
    }
    cur->extend();
    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);
            if (val < MAXC) upd(val+1, val);
        }
        ++nho[val];
    }
    for (int i = 0; i < coinsCount; i++) {
        int64_t val = coins[i];
        if (val < MAXC) upd(val+1, val);
    }
    return (root.minprefix >= -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);
                if (val < MAXC) upd(val+1, val);
            } else if (nho[val] == 0) {
                upd(val, -val);
                if (val < MAXC) upd(val+1, val);
            }
            ++nho[val];
        } else {
            --nho[val];
            if (nho[val] == 0) {
                upd(val, val);
                if (val < MAXC) upd(val+1, -val);
            }
        }
        if (val < MAXC) upd(val+1, event * val);
    }
    return (root.minprefix >= -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 600 KB Output is correct
2 Correct 0 ms 344 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 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 344 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 348 KB Output is correct
6 Correct 6 ms 3420 KB Output is correct
7 Correct 6 ms 3676 KB Output is correct
8 Correct 56 ms 28256 KB Output is correct
9 Correct 57 ms 28600 KB Output is correct
10 Correct 50 ms 27732 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 344 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 348 KB Output is correct
6 Correct 710 ms 73092 KB Output is correct
7 Correct 699 ms 72020 KB Output is correct
8 Correct 685 ms 73040 KB Output is correct
9 Correct 1129 ms 92160 KB Output is correct
10 Correct 1137 ms 98700 KB Output is correct
11 Correct 341 ms 58964 KB Output is correct
12 Correct 353 ms 59216 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 344 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 348 KB Output is correct
6 Correct 6 ms 3420 KB Output is correct
7 Correct 6 ms 3676 KB Output is correct
8 Correct 56 ms 28256 KB Output is correct
9 Correct 57 ms 28600 KB Output is correct
10 Correct 50 ms 27732 KB Output is correct
11 Correct 710 ms 73092 KB Output is correct
12 Correct 699 ms 72020 KB Output is correct
13 Correct 685 ms 73040 KB Output is correct
14 Correct 1129 ms 92160 KB Output is correct
15 Correct 1137 ms 98700 KB Output is correct
16 Correct 341 ms 58964 KB Output is correct
17 Correct 353 ms 59216 KB Output is correct
18 Correct 1603 ms 457768 KB Output is correct
19 Correct 1669 ms 475932 KB Output is correct
20 Runtime error 1395 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -