oj.uz

Submission #703892

# Submission time Handle Problem Language Result Execution time Memory
703892 2023-02-28T19:08:40 Z mihai145 Happiness (Balkan15_HAPPINESS) C++17
100 / 100
 1239 ms 502248 KB 
#include <algorithm>
#include <cmath>
#include "happiness.h"

using namespace std;

const int K = 5;
const int Q = 100000;

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(long long max_sz) {
        int lg = max(1, min((int)log2(max_sz), 8)); // :(
        int sz = 4 * Q * K * lg;

        v = new State[sz];
        sons = new pair<int, int>[sz];

        for (int i = 1; i < sz; 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(maxCoinSize);
    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 158 ms 375912 KB Output is correct
2 Correct 164 ms 375928 KB Output is correct
3 Correct 166 ms 375980 KB Output is correct
4 Correct 188 ms 375952 KB Output is correct
5 Correct 163 ms 375960 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 375912 KB Output is correct
2 Correct 164 ms 375928 KB Output is correct
3 Correct 166 ms 375980 KB Output is correct
4 Correct 188 ms 375952 KB Output is correct
5 Correct 163 ms 375960 KB Output is correct
6 Correct 225 ms 501212 KB Output is correct
7 Correct 239 ms 501288 KB Output is correct
8 Correct 277 ms 501348 KB Output is correct
9 Correct 236 ms 501304 KB Output is correct
10 Correct 237 ms 501400 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 375912 KB Output is correct
2 Correct 164 ms 375928 KB Output is correct
3 Correct 166 ms 375980 KB Output is correct
4 Correct 188 ms 375952 KB Output is correct
5 Correct 163 ms 375960 KB Output is correct
6 Correct 571 ms 502204 KB Output is correct
7 Correct 559 ms 502160 KB Output is correct
8 Correct 537 ms 502192 KB Output is correct
9 Correct 727 ms 502236 KB Output is correct
10 Correct 721 ms 502244 KB Output is correct
11 Correct 387 ms 501380 KB Output is correct
12 Correct 410 ms 501464 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 375912 KB Output is correct
2 Correct 164 ms 375928 KB Output is correct
3 Correct 166 ms 375980 KB Output is correct
4 Correct 188 ms 375952 KB Output is correct
5 Correct 163 ms 375960 KB Output is correct
6 Correct 225 ms 501212 KB Output is correct
7 Correct 239 ms 501288 KB Output is correct
8 Correct 277 ms 501348 KB Output is correct
9 Correct 236 ms 501304 KB Output is correct
10 Correct 237 ms 501400 KB Output is correct
11 Correct 571 ms 502204 KB Output is correct
12 Correct 559 ms 502160 KB Output is correct
13 Correct 537 ms 502192 KB Output is correct
14 Correct 727 ms 502236 KB Output is correct
15 Correct 721 ms 502244 KB Output is correct
16 Correct 387 ms 501380 KB Output is correct
17 Correct 410 ms 501464 KB Output is correct
18 Correct 805 ms 502184 KB Output is correct
19 Correct 815 ms 502240 KB Output is correct
20 Correct 1239 ms 502232 KB Output is correct
21 Correct 778 ms 502236 KB Output is correct
22 Correct 482 ms 501424 KB Output is correct
23 Correct 496 ms 501448 KB Output is correct
24 Correct 759 ms 502248 KB Output is correct