oj.uz

Submission #703877

# Submission time Handle Problem Language Result Execution time Memory
703877 2023-02-28T18:48:04 Z mihai145 Happiness (Balkan15_HAPPINESS) C++17
40 / 100
 564 ms 131084 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;
            v[i].valid = false;
        }
        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 * pos;
            v[idx].range_min = ((v[idx].range_sum > 0) ? pos : 0);
            v[idx].valid = true;
            return;
        }

        long long 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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 125432 KB Output is correct
2 Correct 60 ms 125520 KB Output is correct
3 Correct 54 ms 125416 KB Output is correct
4 Correct 56 ms 125452 KB Output is correct
5 Correct 58 ms 125424 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 125432 KB Output is correct
2 Correct 60 ms 125520 KB Output is correct
3 Correct 54 ms 125416 KB Output is correct
4 Correct 56 ms 125452 KB Output is correct
5 Correct 58 ms 125424 KB Output is correct
6 Incorrect 51 ms 125508 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 125432 KB Output is correct
2 Correct 60 ms 125520 KB Output is correct
3 Correct 54 ms 125416 KB Output is correct
4 Correct 56 ms 125452 KB Output is correct
5 Correct 58 ms 125424 KB Output is correct
6 Correct 370 ms 129556 KB Output is correct
7 Correct 373 ms 129664 KB Output is correct
8 Correct 370 ms 129648 KB Output is correct
9 Correct 540 ms 130940 KB Output is correct
10 Correct 564 ms 131084 KB Output is correct
11 Correct 219 ms 129400 KB Output is correct
12 Correct 210 ms 129532 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 125432 KB Output is correct
2 Correct 60 ms 125520 KB Output is correct
3 Correct 54 ms 125416 KB Output is correct
4 Correct 56 ms 125452 KB Output is correct
5 Correct 58 ms 125424 KB Output is correct
6 Incorrect 51 ms 125508 KB Output isn't correct
7 Halted 0 ms 0 KB -