oj.uz

답안 #704129

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
704129 2023-03-01T16:15:05 Z mihai145 Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 1227 ms 524288 KB 
// Test problem: https://oj.uz/problem/view/Balkan15_HAPPINESS
// Reusing vertices

#include <vector>
#include "happiness.h"

using namespace std;

const int LOG = 15; // should be ~40
const int MAX_N = 200000;
const int SZ = 4 * MAX_N * LOG;

class DynamicSegmentTree {
private:
    struct State {
        long long range_sum, range_min;
        bool ok;
    };
    State v[SZ];
    pair<int, int> sons[SZ];

    vector<int> available;

    void clear(int idx) {
        v[idx].range_sum = v[idx].range_min = 0;
        sons[idx].first = sons[idx].second = -1;
        v[idx].ok = true;
    }

    void init(int idx) {
        if (sons[idx].first == -1) {
            sons[idx].first = available.back(), available.pop_back();
        }
        if (sons[idx].second == -1) {
            sons[idx].second = available.back(), available.pop_back();
        }
    }

    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.ok = a.ok && (1 + a.range_sum >= b.range_min);

        return res;
    }

public:
    void Init() {
        for (int i = SZ - 1; i >= 1; i--) {
            available.push_back(i);
            clear(i);
        }
        available.pop_back();
    }

    void Update(int idx, long long l, long long r, long long pos, int sgn, int par = -1) {
        if (sons[idx].first == -1 || sons[idx].second == -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].ok = true;

            if (v[idx].range_sum == 0) {
                if (par == -1) return;
                if (sons[par].first == idx) { sons[par].first = -1; }
                else { sons[par].second = -1; }
                clear(idx);
                available.push_back(idx);
            }
            return;
        }

        long long mid = (l + r) >> 1;
        if (pos <= mid) Update(sons[idx].first, l, mid, pos, sgn, idx);
        else Update(sons[idx].second, mid + 1, r, pos, sgn, idx);

        if (sons[idx].first == -1) {
            v[idx] = (sons[idx].second != -1 ? v[sons[idx].second] : State{0, 0,true});
        } else {
            v[idx] = merge(v[sons[idx].first], (sons[idx].second != -1 ? v[sons[idx].second] : State{0, 0,true}));
        }
    }

    bool GetValid() {
        return v[1].ok;
    }
};

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);
        if (coins[i] == 1) fv_1 += 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

# 결과 실행 시간 메모리 Grader output
1 Correct 213 ms 423008 KB Output is correct
2 Correct 221 ms 423068 KB Output is correct
3 Correct 211 ms 423072 KB Output is correct
4 Correct 212 ms 423256 KB Output is correct
5 Correct 219 ms 423088 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 213 ms 423008 KB Output is correct
2 Correct 221 ms 423068 KB Output is correct
3 Correct 211 ms 423072 KB Output is correct
4 Correct 212 ms 423256 KB Output is correct
5 Correct 219 ms 423088 KB Output is correct
6 Correct 216 ms 423080 KB Output is correct
7 Correct 213 ms 423120 KB Output is correct
8 Correct 229 ms 423184 KB Output is correct
9 Correct 230 ms 423164 KB Output is correct
10 Correct 226 ms 423116 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 213 ms 423008 KB Output is correct
2 Correct 221 ms 423068 KB Output is correct
3 Correct 211 ms 423072 KB Output is correct
4 Correct 212 ms 423256 KB Output is correct
5 Correct 219 ms 423088 KB Output is correct
6 Correct 521 ms 424080 KB Output is correct
7 Correct 505 ms 424176 KB Output is correct
8 Correct 519 ms 423976 KB Output is correct
9 Correct 700 ms 424092 KB Output is correct
10 Correct 700 ms 424048 KB Output is correct
11 Correct 374 ms 423288 KB Output is correct
12 Correct 373 ms 423260 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 213 ms 423008 KB Output is correct
2 Correct 221 ms 423068 KB Output is correct
3 Correct 211 ms 423072 KB Output is correct
4 Correct 212 ms 423256 KB Output is correct
5 Correct 219 ms 423088 KB Output is correct
6 Correct 216 ms 423080 KB Output is correct
7 Correct 213 ms 423120 KB Output is correct
8 Correct 229 ms 423184 KB Output is correct
9 Correct 230 ms 423164 KB Output is correct
10 Correct 226 ms 423116 KB Output is correct
11 Correct 521 ms 424080 KB Output is correct
12 Correct 505 ms 424176 KB Output is correct
13 Correct 519 ms 423976 KB Output is correct
14 Correct 700 ms 424092 KB Output is correct
15 Correct 700 ms 424048 KB Output is correct
16 Correct 374 ms 423288 KB Output is correct
17 Correct 373 ms 423260 KB Output is correct
18 Correct 899 ms 424408 KB Output is correct
19 Correct 843 ms 426528 KB Output is correct
20 Runtime error 1227 ms 524288 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -