oj.uz

Submission #704132

# Submission time Handle Problem Language Result Execution time Memory
704132 2023-03-01T16:23:19 Z mihai145 Happiness (Balkan15_HAPPINESS) C++17
100 / 100
 1150 ms 443820 KB 
// Test problem: https://oj.uz/problem/view/Balkan15_HAPPINESS
// Reusing vertices

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

using namespace std;

const int LOG = 20; // 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;

    // messy tricks to reduce memory
    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 233 ms 438696 KB Output is correct
2 Correct 230 ms 438732 KB Output is correct
3 Correct 231 ms 438768 KB Output is correct
4 Correct 238 ms 438756 KB Output is correct
5 Correct 230 ms 438696 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 438696 KB Output is correct
2 Correct 230 ms 438732 KB Output is correct
3 Correct 231 ms 438768 KB Output is correct
4 Correct 238 ms 438756 KB Output is correct
5 Correct 230 ms 438696 KB Output is correct
6 Correct 231 ms 438696 KB Output is correct
7 Correct 249 ms 438824 KB Output is correct
8 Correct 242 ms 438768 KB Output is correct
9 Correct 250 ms 438800 KB Output is correct
10 Correct 248 ms 438848 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 438696 KB Output is correct
2 Correct 230 ms 438732 KB Output is correct
3 Correct 231 ms 438768 KB Output is correct
4 Correct 238 ms 438756 KB Output is correct
5 Correct 230 ms 438696 KB Output is correct
6 Correct 523 ms 439720 KB Output is correct
7 Correct 514 ms 439648 KB Output is correct
8 Correct 530 ms 439704 KB Output is correct
9 Correct 714 ms 439988 KB Output is correct
10 Correct 708 ms 439668 KB Output is correct
11 Correct 414 ms 438940 KB Output is correct
12 Correct 406 ms 439108 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 438696 KB Output is correct
2 Correct 230 ms 438732 KB Output is correct
3 Correct 231 ms 438768 KB Output is correct
4 Correct 238 ms 438756 KB Output is correct
5 Correct 230 ms 438696 KB Output is correct
6 Correct 231 ms 438696 KB Output is correct
7 Correct 249 ms 438824 KB Output is correct
8 Correct 242 ms 438768 KB Output is correct
9 Correct 250 ms 438800 KB Output is correct
10 Correct 248 ms 438848 KB Output is correct
11 Correct 523 ms 439720 KB Output is correct
12 Correct 514 ms 439648 KB Output is correct
13 Correct 530 ms 439704 KB Output is correct
14 Correct 714 ms 439988 KB Output is correct
15 Correct 708 ms 439668 KB Output is correct
16 Correct 414 ms 438940 KB Output is correct
17 Correct 406 ms 439108 KB Output is correct
18 Correct 862 ms 439928 KB Output is correct
19 Correct 826 ms 439716 KB Output is correct
20 Correct 1150 ms 443820 KB Output is correct
21 Correct 792 ms 442280 KB Output is correct
22 Correct 518 ms 443452 KB Output is correct
23 Correct 540 ms 441288 KB Output is correct
24 Correct 819 ms 441984 KB Output is correct