oj.uz

Submission #1091168

# Submission time Handle Problem Language Result Execution time Memory
1091168 2024-09-20T01:32:01 Z anmattroi Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 2000 ms 434852 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;
    bool L = 0, R = 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 extend_left() {
        if (!L) {left_child = new vertex; L = 1;}

    }
    void extend_right() {
        if (!R) {right_child = new vertex; R = 1;}
    }

    void up() {
        sum = (L ? left_child->sum : 0) + (R ? right_child->sum : 0);
        minprefix = min((L ? left_child->minprefix : 0), (L ? left_child->sum : 0) + (R ? right_child->minprefix : 0));
    }
};

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;
    }
    int64_t mid = (lo + hi) >> 1LL;
    if (u <= mid) {
        cur->extend_left();
        upd(u, d, cur->left_child, lo, mid);
    } else {
        cur->extend_right();
        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 1 ms 440 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 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 1 ms 440 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 4 ms 2136 KB Output is correct
7 Correct 4 ms 2140 KB Output is correct
8 Correct 43 ms 15864 KB Output is correct
9 Correct 53 ms 16212 KB Output is correct
10 Correct 37 ms 15324 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 440 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 641 ms 59764 KB Output is correct
7 Correct 639 ms 59024 KB Output is correct
8 Correct 709 ms 59892 KB Output is correct
9 Correct 1067 ms 78928 KB Output is correct
10 Correct 1172 ms 86096 KB Output is correct
11 Correct 317 ms 59268 KB Output is correct
12 Correct 336 ms 59220 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 440 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 4 ms 2136 KB Output is correct
7 Correct 4 ms 2140 KB Output is correct
8 Correct 43 ms 15864 KB Output is correct
9 Correct 53 ms 16212 KB Output is correct
10 Correct 37 ms 15324 KB Output is correct
11 Correct 641 ms 59764 KB Output is correct
12 Correct 639 ms 59024 KB Output is correct
13 Correct 709 ms 59892 KB Output is correct
14 Correct 1067 ms 78928 KB Output is correct
15 Correct 1172 ms 86096 KB Output is correct
16 Correct 317 ms 59268 KB Output is correct
17 Correct 336 ms 59220 KB Output is correct
18 Correct 1332 ms 257616 KB Output is correct
19 Correct 1346 ms 267540 KB Output is correct
20 Execution timed out 2108 ms 434852 KB Time limit exceeded
21 Halted 0 ms 0 KB -