oj.uz

Submission #704131

# Submission time Handle Problem Language Result Execution time Memory
704131 2023-03-01T16:22:15 Z mihai145 Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 1410 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 = 18; // 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_ok;
    };
    State v[SZ];
    pair<int, int> sons[SZ];

    vector<int> available;

    long long encode(long long val, bool ok) {
        return val * 10 + ok;
    }

    pair<long long, bool> decode(long long val) {
        return {val / 10, (val % 10 == 1)};
    }

    void clear(int idx) {
        v[idx].range_sum = 0;
        v[idx].range_min_ok = encode(0, true);
        sons[idx].first = sons[idx].second = -1;
    }

    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;
        pair<long long, bool> ark = decode(a.range_min_ok), brk = decode(b.range_min_ok);

        long long range_min;
        if (min(ark.first, brk.first) > 0) {
            range_min = min(ark.first, brk.first);
        } else {
            range_min = max(ark.first, brk.first);
        }
        bool ok = ark.second && (1 + a.range_sum >= brk.first);

        res.range_min_ok = encode(range_min, ok);
        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_ok = encode(((v[idx].range_sum > 0) ? pos : 0), 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, encode(0, true)});
        } else {
            v[idx] = merge(v[sons[idx].first], (sons[idx].second != -1 ? v[sons[idx].second] : State{0, encode(0, true)}));
        }
    }

    bool GetValid() {
        return decode(v[1].range_min_ok).second;
    }
};

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 210 ms 394928 KB Output is correct
2 Correct 217 ms 394844 KB Output is correct
3 Correct 208 ms 394836 KB Output is correct
4 Correct 209 ms 394856 KB Output is correct
5 Correct 208 ms 394832 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 394928 KB Output is correct
2 Correct 217 ms 394844 KB Output is correct
3 Correct 208 ms 394836 KB Output is correct
4 Correct 209 ms 394856 KB Output is correct
5 Correct 208 ms 394832 KB Output is correct
6 Correct 208 ms 394852 KB Output is correct
7 Correct 208 ms 394964 KB Output is correct
8 Correct 223 ms 394908 KB Output is correct
9 Correct 222 ms 394988 KB Output is correct
10 Correct 219 ms 394944 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 394928 KB Output is correct
2 Correct 217 ms 394844 KB Output is correct
3 Correct 208 ms 394836 KB Output is correct
4 Correct 209 ms 394856 KB Output is correct
5 Correct 208 ms 394832 KB Output is correct
6 Correct 514 ms 395960 KB Output is correct
7 Correct 493 ms 395836 KB Output is correct
8 Correct 507 ms 395880 KB Output is correct
9 Correct 709 ms 395912 KB Output is correct
10 Correct 714 ms 396068 KB Output is correct
11 Correct 380 ms 395048 KB Output is correct
12 Correct 386 ms 395160 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 394928 KB Output is correct
2 Correct 217 ms 394844 KB Output is correct
3 Correct 208 ms 394836 KB Output is correct
4 Correct 209 ms 394856 KB Output is correct
5 Correct 208 ms 394832 KB Output is correct
6 Correct 208 ms 394852 KB Output is correct
7 Correct 208 ms 394964 KB Output is correct
8 Correct 223 ms 394908 KB Output is correct
9 Correct 222 ms 394988 KB Output is correct
10 Correct 219 ms 394944 KB Output is correct
11 Correct 514 ms 395960 KB Output is correct
12 Correct 493 ms 395836 KB Output is correct
13 Correct 507 ms 395880 KB Output is correct
14 Correct 709 ms 395912 KB Output is correct
15 Correct 714 ms 396068 KB Output is correct
16 Correct 380 ms 395048 KB Output is correct
17 Correct 386 ms 395160 KB Output is correct
18 Correct 825 ms 395888 KB Output is correct
19 Correct 808 ms 395916 KB Output is correct
20 Runtime error 1410 ms 524288 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -