oj.uz

Submission #703881

# Submission time Handle Problem Language Result Execution time Memory
703881 2023-02-28T18:54:00 Z mihai145 Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 890 ms 524288 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, 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 132 ms 313368 KB Output is correct
2 Correct 144 ms 313348 KB Output is correct
3 Correct 139 ms 313356 KB Output is correct
4 Correct 136 ms 313344 KB Output is correct
5 Correct 137 ms 313392 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 313368 KB Output is correct
2 Correct 144 ms 313348 KB Output is correct
3 Correct 139 ms 313356 KB Output is correct
4 Correct 136 ms 313344 KB Output is correct
5 Correct 137 ms 313392 KB Output is correct
6 Correct 139 ms 313348 KB Output is correct
7 Correct 143 ms 313400 KB Output is correct
8 Correct 151 ms 313580 KB Output is correct
9 Correct 148 ms 313584 KB Output is correct
10 Correct 146 ms 313548 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 313368 KB Output is correct
2 Correct 144 ms 313348 KB Output is correct
3 Correct 139 ms 313356 KB Output is correct
4 Correct 136 ms 313344 KB Output is correct
5 Correct 137 ms 313392 KB Output is correct
6 Correct 425 ms 314280 KB Output is correct
7 Correct 462 ms 314348 KB Output is correct
8 Correct 427 ms 314360 KB Output is correct
9 Correct 625 ms 314372 KB Output is correct
10 Correct 634 ms 314484 KB Output is correct
11 Correct 294 ms 313560 KB Output is correct
12 Correct 293 ms 313548 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 313368 KB Output is correct
2 Correct 144 ms 313348 KB Output is correct
3 Correct 139 ms 313356 KB Output is correct
4 Correct 136 ms 313344 KB Output is correct
5 Correct 137 ms 313392 KB Output is correct
6 Correct 139 ms 313348 KB Output is correct
7 Correct 143 ms 313400 KB Output is correct
8 Correct 151 ms 313580 KB Output is correct
9 Correct 148 ms 313584 KB Output is correct
10 Correct 146 ms 313548 KB Output is correct
11 Correct 425 ms 314280 KB Output is correct
12 Correct 462 ms 314348 KB Output is correct
13 Correct 427 ms 314360 KB Output is correct
14 Correct 625 ms 314372 KB Output is correct
15 Correct 634 ms 314484 KB Output is correct
16 Correct 294 ms 313560 KB Output is correct
17 Correct 293 ms 313548 KB Output is correct
18 Correct 711 ms 319736 KB Output is correct
19 Correct 714 ms 319828 KB Output is correct
20 Runtime error 890 ms 524288 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -