oj.uz

Submission #703884

# Submission time Handle Problem Language Result Execution time Memory
703884 2023-02-28T18:59:25 Z mihai145 Happiness (Balkan15_HAPPINESS) C++14
100 / 100
 1109 ms 510212 KB 
#include <algorithm>
#include "happiness.h"

using namespace std;

const int K = 5;
const int LG = 8;
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, long long 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 216 ms 501276 KB Output is correct
2 Correct 212 ms 501188 KB Output is correct
3 Correct 210 ms 501172 KB Output is correct
4 Correct 239 ms 501332 KB Output is correct
5 Correct 208 ms 501172 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 501276 KB Output is correct
2 Correct 212 ms 501188 KB Output is correct
3 Correct 210 ms 501172 KB Output is correct
4 Correct 239 ms 501332 KB Output is correct
5 Correct 208 ms 501172 KB Output is correct
6 Correct 210 ms 501184 KB Output is correct
7 Correct 221 ms 501300 KB Output is correct
8 Correct 237 ms 501268 KB Output is correct
9 Correct 233 ms 501240 KB Output is correct
10 Correct 225 ms 501384 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 501276 KB Output is correct
2 Correct 212 ms 501188 KB Output is correct
3 Correct 210 ms 501172 KB Output is correct
4 Correct 239 ms 501332 KB Output is correct
5 Correct 208 ms 501172 KB Output is correct
6 Correct 501 ms 502188 KB Output is correct
7 Correct 499 ms 502220 KB Output is correct
8 Correct 507 ms 502388 KB Output is correct
9 Correct 694 ms 502232 KB Output is correct
10 Correct 686 ms 502320 KB Output is correct
11 Correct 366 ms 501488 KB Output is correct
12 Correct 359 ms 501452 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 501276 KB Output is correct
2 Correct 212 ms 501188 KB Output is correct
3 Correct 210 ms 501172 KB Output is correct
4 Correct 239 ms 501332 KB Output is correct
5 Correct 208 ms 501172 KB Output is correct
6 Correct 210 ms 501184 KB Output is correct
7 Correct 221 ms 501300 KB Output is correct
8 Correct 237 ms 501268 KB Output is correct
9 Correct 233 ms 501240 KB Output is correct
10 Correct 225 ms 501384 KB Output is correct
11 Correct 501 ms 502188 KB Output is correct
12 Correct 499 ms 502220 KB Output is correct
13 Correct 507 ms 502388 KB Output is correct
14 Correct 694 ms 502232 KB Output is correct
15 Correct 686 ms 502320 KB Output is correct
16 Correct 366 ms 501488 KB Output is correct
17 Correct 359 ms 501452 KB Output is correct
18 Correct 768 ms 502328 KB Output is correct
19 Correct 794 ms 502244 KB Output is correct
20 Correct 1109 ms 510212 KB Output is correct
21 Correct 733 ms 507032 KB Output is correct
22 Correct 468 ms 507176 KB Output is correct
23 Correct 470 ms 507720 KB Output is correct
24 Correct 881 ms 507604 KB Output is correct