oj.uz

Submission #1091171

# Submission time Handle Problem Language Result Execution time Memory
1091171 2024-09-20T01:37:57 Z anmattroi Happiness (Balkan15_HAPPINESS) C++14
100 / 100
 1974 ms 435028 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 Lup() {
        sum = left_child->sum + (R ? right_child->sum : 0);
        minprefix = min(left_child->minprefix, left_child->sum + (R ? right_child->minprefix : 0));
    }
    void Rup() {
        sum = (L ? left_child->sum : 0) + right_child->sum;
        minprefix = min((L ? left_child->minprefix : 0), (L ? left_child->sum : 0) + 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);
        cur->Lup();
    } else {
        cur->extend_right();
        upd(u, d, cur->right_child, mid + 1, hi);
        cur->Rup();
    }
}


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 344 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 0 ms 344 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 5 ms 2140 KB Output is correct
8 Correct 43 ms 15704 KB Output is correct
9 Correct 39 ms 15952 KB Output is correct
10 Correct 36 ms 15476 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 627 ms 59812 KB Output is correct
7 Correct 625 ms 58960 KB Output is correct
8 Correct 647 ms 59804 KB Output is correct
9 Correct 1036 ms 78992 KB Output is correct
10 Correct 1158 ms 85972 KB Output is correct
11 Correct 323 ms 58964 KB Output is correct
12 Correct 339 ms 59220 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 5 ms 2140 KB Output is correct
8 Correct 43 ms 15704 KB Output is correct
9 Correct 39 ms 15952 KB Output is correct
10 Correct 36 ms 15476 KB Output is correct
11 Correct 627 ms 59812 KB Output is correct
12 Correct 625 ms 58960 KB Output is correct
13 Correct 647 ms 59804 KB Output is correct
14 Correct 1036 ms 78992 KB Output is correct
15 Correct 1158 ms 85972 KB Output is correct
16 Correct 323 ms 58964 KB Output is correct
17 Correct 339 ms 59220 KB Output is correct
18 Correct 1264 ms 257616 KB Output is correct
19 Correct 1298 ms 267600 KB Output is correct
20 Correct 1974 ms 435028 KB Output is correct
21 Correct 1194 ms 227548 KB Output is correct
22 Correct 516 ms 61008 KB Output is correct
23 Correct 541 ms 61660 KB Output is correct
24 Correct 1250 ms 248024 KB Output is correct