oj.uz

Submission #703886

# Submission time Handle Problem Language Result Execution time Memory
703886 2023-02-28T19:03:51 Z mihai145 Happiness (Balkan15_HAPPINESS) C++14
100 / 100
 1215 ms 372408 KB 
/*
#include <algorithm>
#include "happiness.h"

using namespace std;

const int K = 5;
const int LG = 8; // should be 40???
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();
}
*/

#include "happiness.h"

struct Node {
    long long l, r, val;
    Node *lc, *rc;

    Node(long long L, long long R): l(L), r(R), val(0), lc(nullptr), rc(nullptr) {}

    void update(long long p, long long v) {
        val += v;
        if (l != r) {
            long long mid = (l + r) / 2;
            if (p > mid) {
                if (!rc) rc = new Node(mid + 1, r);
                rc->update(p, v);
            } else {
                if (!lc) lc = new Node(l, mid);
                lc->update(p, v);
            }
        }
    }

    long long query(long long a, long long b) {
        if (r < a || l > b) return 0;
        if (r <= b && l >= a) return val;
        long long ret = 0;
        if (lc) ret += lc->query(a, b);
        if (rc) ret += rc->query(a, b);
        return ret;
    }
};

Node *root;

bool check() {
    long long curr = 1, sm = root->val;
    while (curr < sm) {
        long long t = root->query(1, curr);
        if (t < curr) return false;
        curr = t + 1;
    }
    return true;
}

bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
    root = new Node(1, maxCoinSize);
    for (int i = 0; i < coinsCount; i++) root->update(coins[i], coins[i]);
    return check();
}

bool is_happy(int event, int coinsCount, long long coins[]) {
    for (int i = 0; i < coinsCount; i++) root->update(coins[i], event * coins[i]);
    return check();
}

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 0 ms 212 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 1768 KB Output is correct
7 Correct 3 ms 1972 KB Output is correct
8 Correct 25 ms 13992 KB Output is correct
9 Correct 24 ms 14156 KB Output is correct
10 Correct 23 ms 13700 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 357 ms 34416 KB Output is correct
7 Correct 380 ms 34012 KB Output is correct
8 Correct 386 ms 34504 KB Output is correct
9 Correct 515 ms 44360 KB Output is correct
10 Correct 544 ms 48308 KB Output is correct
11 Correct 143 ms 33420 KB Output is correct
12 Correct 138 ms 33460 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 1768 KB Output is correct
7 Correct 3 ms 1972 KB Output is correct
8 Correct 25 ms 13992 KB Output is correct
9 Correct 24 ms 14156 KB Output is correct
10 Correct 23 ms 13700 KB Output is correct
11 Correct 357 ms 34416 KB Output is correct
12 Correct 380 ms 34012 KB Output is correct
13 Correct 386 ms 34504 KB Output is correct
14 Correct 515 ms 44360 KB Output is correct
15 Correct 544 ms 48308 KB Output is correct
16 Correct 143 ms 33420 KB Output is correct
17 Correct 138 ms 33460 KB Output is correct
18 Correct 846 ms 220448 KB Output is correct
19 Correct 860 ms 229264 KB Output is correct
20 Correct 1215 ms 372408 KB Output is correct
21 Correct 652 ms 194472 KB Output is correct
22 Correct 178 ms 33492 KB Output is correct
23 Correct 201 ms 33564 KB Output is correct
24 Correct 904 ms 211404 KB Output is correct