oj.uz

Submission #703880

# Submission time Handle Problem Language Result Execution time Memory
703880 2023-02-28T18:52:38 Z mihai145 Happiness (Balkan15_HAPPINESS) C++17
40 / 100
 681 ms 314380 KB 
#include <algorithm>
#include "happiness.h"

using namespace std;

const int K = 5;
const int LG = 5;
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 146 ms 313380 KB Output is correct
2 Correct 136 ms 313308 KB Output is correct
3 Correct 141 ms 313308 KB Output is correct
4 Correct 139 ms 313292 KB Output is correct
5 Correct 146 ms 313288 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 313380 KB Output is correct
2 Correct 136 ms 313308 KB Output is correct
3 Correct 141 ms 313308 KB Output is correct
4 Correct 139 ms 313292 KB Output is correct
5 Correct 146 ms 313288 KB Output is correct
6 Incorrect 148 ms 313300 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 146 ms 313380 KB Output is correct
2 Correct 136 ms 313308 KB Output is correct
3 Correct 141 ms 313308 KB Output is correct
4 Correct 139 ms 313292 KB Output is correct
5 Correct 146 ms 313288 KB Output is correct
6 Correct 489 ms 314304 KB Output is correct
7 Correct 473 ms 314308 KB Output is correct
8 Correct 491 ms 314300 KB Output is correct
9 Correct 681 ms 314352 KB Output is correct
10 Correct 655 ms 314380 KB Output is correct
11 Correct 285 ms 313544 KB Output is correct
12 Correct 287 ms 313656 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 313380 KB Output is correct
2 Correct 136 ms 313308 KB Output is correct
3 Correct 141 ms 313308 KB Output is correct
4 Correct 139 ms 313292 KB Output is correct
5 Correct 146 ms 313288 KB Output is correct
6 Incorrect 148 ms 313300 KB Output isn't correct
7 Halted 0 ms 0 KB -