oj.uz

Submission #704126

# Submission time Handle Problem Language Result Execution time Memory
704126 2023-03-01T16:11:52 Z mihai145 Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 889 ms 524288 KB 
// Test problem: https://oj.uz/problem/view/Balkan15_HAPPINESS

#include <vector>
#include "happiness.h"

using namespace std;

const int LOG = 10; // should be ~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 clear(int idx) {
        v[idx].range_sum = v[idx].range_min = 0;
        sons[idx].first = sons[idx].second = -1;
        v[idx].ok = true;
    }

    void init(int idx) {
        if (sons[idx].first == -1) {
            sons[idx].first = available.back(), available.pop_back();
        }
        if (sons[idx].second == -1) {
            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);
            clear(i);
        }
        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);
        }

        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; }
                clear(idx);
                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);

        if (sons[idx].first == -1) {
            v[idx] = (sons[idx].second != -1 ? v[sons[idx].second] : State{0, 0,true});
        } else {
            v[idx] = merge(v[sons[idx].first], (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);
        if (coins[i] == 1) fv_1 += event;
    }

    return get_is_happy();
}

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 140 ms 282096 KB Output is correct
2 Correct 150 ms 282164 KB Output is correct
3 Correct 135 ms 282156 KB Output is correct
4 Correct 138 ms 282220 KB Output is correct
5 Correct 137 ms 282120 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 282096 KB Output is correct
2 Correct 150 ms 282164 KB Output is correct
3 Correct 135 ms 282156 KB Output is correct
4 Correct 138 ms 282220 KB Output is correct
5 Correct 137 ms 282120 KB Output is correct
6 Correct 143 ms 282140 KB Output is correct
7 Correct 139 ms 282232 KB Output is correct
8 Correct 151 ms 282476 KB Output is correct
9 Correct 157 ms 282476 KB Output is correct
10 Correct 153 ms 282376 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 282096 KB Output is correct
2 Correct 150 ms 282164 KB Output is correct
3 Correct 135 ms 282156 KB Output is correct
4 Correct 138 ms 282220 KB Output is correct
5 Correct 137 ms 282120 KB Output is correct
6 Correct 442 ms 285544 KB Output is correct
7 Correct 431 ms 285468 KB Output is correct
8 Correct 466 ms 285548 KB Output is correct
9 Correct 633 ms 285484 KB Output is correct
10 Correct 653 ms 285480 KB Output is correct
11 Correct 316 ms 284732 KB Output is correct
12 Correct 314 ms 284676 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 282096 KB Output is correct
2 Correct 150 ms 282164 KB Output is correct
3 Correct 135 ms 282156 KB Output is correct
4 Correct 138 ms 282220 KB Output is correct
5 Correct 137 ms 282120 KB Output is correct
6 Correct 143 ms 282140 KB Output is correct
7 Correct 139 ms 282232 KB Output is correct
8 Correct 151 ms 282476 KB Output is correct
9 Correct 157 ms 282476 KB Output is correct
10 Correct 153 ms 282376 KB Output is correct
11 Correct 442 ms 285544 KB Output is correct
12 Correct 431 ms 285468 KB Output is correct
13 Correct 466 ms 285548 KB Output is correct
14 Correct 633 ms 285484 KB Output is correct
15 Correct 653 ms 285480 KB Output is correct
16 Correct 316 ms 284732 KB Output is correct
17 Correct 314 ms 284676 KB Output is correct
18 Runtime error 889 ms 524288 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -