oj.uz

Submission #704118

# Submission time Handle Problem Language Result Execution time Memory
704118 2023-03-01T15:55:34 Z mihai145 Happiness (Balkan15_HAPPINESS) C++17
0 / 100
 291 ms 524288 KB 
// Test problem: https://oj.uz/problem/view/Balkan15_HAPPINESS

#include <algorithm>
#include <cmath>
#include "happiness.h"

using namespace std;

const int LOG = 40;
const int MAX_N = 200000;
const int SZ = 4 * MAX_N * LOG;

class DynamicSegmentTree {
private:
    struct State {
        long long range_sum, range_min;
        bool ok;
    };
    State v[SZ];
    pair<int, int> sons[SZ];

    vector<int> available;

    void init(int idx, int par) {
        sons[idx].first = available.back(), available.pop_back();
        sons[idx].second = available.back(), available.pop_back();
    }

    State merge(const State &a, const State &b) {
        State res;
        res.range_sum = a.range_sum + b.range_sum;
        if (min(a.range_min, b.range_min) > 0) {
            res.range_min = min(a.range_min, b.range_min);
        } else {
            res.range_min = max(a.range_min, b.range_min);
        }
        res.ok = a.ok && (1 + a.range_sum >= b.range_min);

        return res;
    }

public:
    void Init() {
        for (int i = SZ - 1; i >= 1; i--) {
            available.push_back(i);
            v[i].range_sum = v[i].range_min = 0;
            sons[i].first = sons[i].second = -1;
            v[i].ok = false;
        }

        available.pop_back();
    }

    void Update(int idx, long long l, long long r, long long pos, int sgn, int par = -1) {
        if (sons[idx].first == -1 || sons[idx].second == -1) {
            init(idx, par);
        }

        if (l == r) {
            v[idx].range_sum += sgn * pos;
            v[idx].range_min = ((v[idx].range_sum > 0) ? pos : 0);
            v[idx].ok = true;

            if (v[idx].range_sum == 0) {
                if (par == -1) return;
                if (sons[par].first == idx) { sons[par].first = -1; }
                else { sons[par].second = -1; }
                available.push_back(idx);
            }

            return;
        }

        long long mid = (l + r) >> 1;
        if (pos <= mid) Update(sons[idx].first, l, mid, pos, sgn, idx);
        else Update(sons[idx].second, mid + 1, r, pos, sgn, idx);

        v[idx] = merge((sons[idx].first != -1 ? v[sons[idx].first] : State{0, 0, true}),
                       {sons[idx].second == -1 ? v[sons[idx].second] : State{0, 0,
                                                                             true}});
    }

    bool GetValid() {
        return v[1].ok;
    }
};

DynamicSegmentTree dst;

int nr_coins, fv_1;
long long max_coin_size;

bool get_is_happy() {
    return (nr_coins == 0) || (fv_1 >= 1 && dst.GetValid());
}

bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
    dst.Init();
    nr_coins = coinsCount;
    max_coin_size = maxCoinSize;

    for (int i = 0; i < coinsCount; i++) {
        dst.Update(1, 1, max_coin_size, coins[i], 1);
        if (coins[i] == 1) fv_1++;
    }

    return get_is_happy();
}

bool is_happy(int event, int coinsCount, long long coins[]) {
    nr_coins += event * coinsCount;
    for (int i = 0; i < coinsCount; i++) {
        dst.Update(1, 1, max_coin_size, coins[i], event);
    }

    return get_is_happy();
}

Compilation message

happiness.cpp: In member function 'void DynamicSegmentTree::Update(int, long long int, long long int, long long int, int, int)':
happiness.cpp:79:68: warning: array subscript -1 is below array bounds of 'DynamicSegmentTree::State [32000000]' [-Warray-bounds]
   79 |                        {sons[idx].second == -1 ? v[sons[idx].second] : State{0, 0,
      |                                                  ~~~~~~~~~~~~~~~~~~^
happiness.cpp:19:11: note: while referencing 'DynamicSegmentTree::v'
   19 |     State v[SZ];
      |           ^
happiness.cpp: In function 'bool is_happy(int, int, long long int*)':
happiness.cpp:79:68: warning: array subscript -1 is below array bounds of 'DynamicSegmentTree::State [32000000]' [-Warray-bounds]
   79 |                        {sons[idx].second == -1 ? v[sons[idx].second] : State{0, 0,
      |                                                  ~~~~~~~~~~~~~~~~~~^
happiness.cpp:19:11: note: while referencing 'DynamicSegmentTree::v'
   19 |     State v[SZ];
      |           ^
happiness.cpp:88:20: note: defined here 'dst'
   88 | DynamicSegmentTree dst;
      |                    ^~~
grader.cpp: In function 'int main()':
grader.cpp:16:12: warning: unused variable 'max_code' [-Wunused-variable]
   16 |  long long max_code;
      |            ^~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 291 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 291 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 291 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 291 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -