oj.uz

Submission #704130

# Submission time Handle Problem Language Result Execution time Memory
704130 2023-03-01T16:16:45 Z mihai145 Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 1509 ms 524288 KB 
// Test problem: https://oj.uz/problem/view/Balkan15_HAPPINESS
// Reusing vertices

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

using namespace std;

const int LOG = 17; // 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 239 ms 479408 KB Output is correct
2 Correct 256 ms 479444 KB Output is correct
3 Correct 240 ms 479364 KB Output is correct
4 Correct 250 ms 479380 KB Output is correct
5 Correct 243 ms 479348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 479408 KB Output is correct
2 Correct 256 ms 479444 KB Output is correct
3 Correct 240 ms 479364 KB Output is correct
4 Correct 250 ms 479380 KB Output is correct
5 Correct 243 ms 479348 KB Output is correct
6 Correct 260 ms 479624 KB Output is correct
7 Correct 251 ms 479432 KB Output is correct
8 Correct 252 ms 479520 KB Output is correct
9 Correct 282 ms 479536 KB Output is correct
10 Correct 251 ms 479496 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 479408 KB Output is correct
2 Correct 256 ms 479444 KB Output is correct
3 Correct 240 ms 479364 KB Output is correct
4 Correct 250 ms 479380 KB Output is correct
5 Correct 243 ms 479348 KB Output is correct
6 Correct 586 ms 480472 KB Output is correct
7 Correct 614 ms 480428 KB Output is correct
8 Correct 540 ms 480436 KB Output is correct
9 Correct 730 ms 480564 KB Output is correct
10 Correct 741 ms 480560 KB Output is correct
11 Correct 408 ms 479656 KB Output is correct
12 Correct 409 ms 479656 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 479408 KB Output is correct
2 Correct 256 ms 479444 KB Output is correct
3 Correct 240 ms 479364 KB Output is correct
4 Correct 250 ms 479380 KB Output is correct
5 Correct 243 ms 479348 KB Output is correct
6 Correct 260 ms 479624 KB Output is correct
7 Correct 251 ms 479432 KB Output is correct
8 Correct 252 ms 479520 KB Output is correct
9 Correct 282 ms 479536 KB Output is correct
10 Correct 251 ms 479496 KB Output is correct
11 Correct 586 ms 480472 KB Output is correct
12 Correct 614 ms 480428 KB Output is correct
13 Correct 540 ms 480436 KB Output is correct
14 Correct 730 ms 480564 KB Output is correct
15 Correct 741 ms 480560 KB Output is correct
16 Correct 408 ms 479656 KB Output is correct
17 Correct 409 ms 479656 KB Output is correct
18 Correct 898 ms 480544 KB Output is correct
19 Correct 875 ms 480472 KB Output is correct
20 Runtime error 1509 ms 524288 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -