oj.uz

Submission #1091164

# Submission time Handle Problem Language Result Execution time Memory
1091164 2024-09-20T01:29:13 Z anmattroi Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 2000 ms 435024 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 extend_left() {
        if (left_child == nullptr) left_child = new vertex;
    }
    void extend_right() {
        if (right_child == nullptr) right_child = new vertex;
    }

    void up() {
        if (left_child == nullptr && right_child == nullptr) {
            sum = 0;
            minprefix = 0;
        } else if (left_child == nullptr) {
            sum = right_child->sum;
            minprefix = min(int64_t(0), right_child->minprefix);
        } else if (right_child == nullptr) {
            sum = left_child->sum;
            minprefix = left_child->minprefix;
        } else {
            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;
    }
    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 0 ms 352 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 1 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 352 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 1 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 5 ms 2140 KB Output is correct
7 Correct 4 ms 2140 KB Output is correct
8 Correct 47 ms 15884 KB Output is correct
9 Correct 56 ms 15992 KB Output is correct
10 Correct 43 ms 15440 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 352 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 1 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 669 ms 59728 KB Output is correct
7 Correct 681 ms 58968 KB Output is correct
8 Correct 698 ms 59856 KB Output is correct
9 Correct 1087 ms 78936 KB Output is correct
10 Correct 1091 ms 86096 KB Output is correct
11 Correct 306 ms 59068 KB Output is correct
12 Correct 325 ms 59224 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 352 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 1 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 5 ms 2140 KB Output is correct
7 Correct 4 ms 2140 KB Output is correct
8 Correct 47 ms 15884 KB Output is correct
9 Correct 56 ms 15992 KB Output is correct
10 Correct 43 ms 15440 KB Output is correct
11 Correct 669 ms 59728 KB Output is correct
12 Correct 681 ms 58968 KB Output is correct
13 Correct 698 ms 59856 KB Output is correct
14 Correct 1087 ms 78936 KB Output is correct
15 Correct 1091 ms 86096 KB Output is correct
16 Correct 306 ms 59068 KB Output is correct
17 Correct 325 ms 59224 KB Output is correct
18 Correct 1231 ms 257612 KB Output is correct
19 Correct 1222 ms 267600 KB Output is correct
20 Execution timed out 2068 ms 435024 KB Time limit exceeded
21 Halted 0 ms 0 KB -