oj.uz

Submission #703883

# Submission time Handle Problem Language Result Execution time Memory
703883 2023-02-28T18:56:25 Z mihai145 Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 1340 ms 524288 KB 
#include <algorithm>
#include "happiness.h"

using namespace std;

const int K = 5;
const int LG = 7;
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 186 ms 438604 KB Output is correct
2 Correct 184 ms 438588 KB Output is correct
3 Correct 183 ms 438604 KB Output is correct
4 Correct 184 ms 438540 KB Output is correct
5 Correct 187 ms 438632 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 438604 KB Output is correct
2 Correct 184 ms 438588 KB Output is correct
3 Correct 183 ms 438604 KB Output is correct
4 Correct 184 ms 438540 KB Output is correct
5 Correct 187 ms 438632 KB Output is correct
6 Correct 185 ms 438604 KB Output is correct
7 Correct 181 ms 438560 KB Output is correct
8 Correct 202 ms 438660 KB Output is correct
9 Correct 209 ms 438616 KB Output is correct
10 Correct 197 ms 438604 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 438604 KB Output is correct
2 Correct 184 ms 438588 KB Output is correct
3 Correct 183 ms 438604 KB Output is correct
4 Correct 184 ms 438540 KB Output is correct
5 Correct 187 ms 438632 KB Output is correct
6 Correct 496 ms 439656 KB Output is correct
7 Correct 464 ms 439572 KB Output is correct
8 Correct 468 ms 439500 KB Output is correct
9 Correct 664 ms 439692 KB Output is correct
10 Correct 669 ms 439780 KB Output is correct
11 Correct 336 ms 438732 KB Output is correct
12 Correct 342 ms 438840 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 438604 KB Output is correct
2 Correct 184 ms 438588 KB Output is correct
3 Correct 183 ms 438604 KB Output is correct
4 Correct 184 ms 438540 KB Output is correct
5 Correct 187 ms 438632 KB Output is correct
6 Correct 185 ms 438604 KB Output is correct
7 Correct 181 ms 438560 KB Output is correct
8 Correct 202 ms 438660 KB Output is correct
9 Correct 209 ms 438616 KB Output is correct
10 Correct 197 ms 438604 KB Output is correct
11 Correct 496 ms 439656 KB Output is correct
12 Correct 464 ms 439572 KB Output is correct
13 Correct 468 ms 439500 KB Output is correct
14 Correct 664 ms 439692 KB Output is correct
15 Correct 669 ms 439780 KB Output is correct
16 Correct 336 ms 438732 KB Output is correct
17 Correct 342 ms 438840 KB Output is correct
18 Correct 740 ms 439564 KB Output is correct
19 Correct 736 ms 439624 KB Output is correct
20 Runtime error 1340 ms 524288 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -