oj.uz

Submission #703876

# Submission time Handle Problem Language Result Execution time Memory
703876 2023-02-28T18:44:35 Z mihai145 Happiness (Balkan15_HAPPINESS) C++14
0 / 100
 50 ms 125516 KB 
#include <algorithm>
#include "happiness.h"

using namespace std;

const int K = 5;
const int LG = 2;
const int Q = 100000;
const int NMAX = LG * K * Q;

class DynamicSegmentTree {
private:
    struct State {
        long long range_sum, range_min;
        bool valid;
    };

    int kNodes;
    State *v;
    pair<int, int> *sons;

    void init(int idx) {
        sons[idx].first = ++kNodes;
        sons[idx].second = ++kNodes;
    }

    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.valid = a.valid && (1 + a.range_sum >= b.range_min);
        return res;
    }

public:
    void Init() {
        v = new State[4 * NMAX];
        sons = new pair<int, int>[4 * NMAX];

        for (int i = 1; i < 4 * NMAX; i++) {
            v[i].range_sum = 0, v[i].range_min = 0;
            sons[i].first = -1, sons[i].second = -1;
        }
        kNodes = 1;
    }

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

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

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

        v[idx] = merge(v[sons[idx].first], v[sons[idx].second]);
    }

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

    ~DynamicSegmentTree() {
        delete v;
        delete sons;
    }
};

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

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 Incorrect 50 ms 125516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 125516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 125516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 125516 KB Output isn't correct
2 Halted 0 ms 0 KB -