oj.uz

Submission #1092120

# Submission time Handle Problem Language Result Execution time Memory
1092120 2024-09-23T08:59:11 Z vijaygomathinayagam Happiness (Balkan15_HAPPINESS) C++17
100 / 100
 998 ms 380256 KB 
#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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 1880 KB Output is correct
7 Correct 2 ms 1884 KB Output is correct
8 Correct 18 ms 14012 KB Output is correct
9 Correct 20 ms 14396 KB Output is correct
10 Correct 17 ms 13840 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 233 ms 36148 KB Output is correct
7 Correct 232 ms 35664 KB Output is correct
8 Correct 274 ms 36304 KB Output is correct
9 Correct 329 ms 46676 KB Output is correct
10 Correct 342 ms 50824 KB Output is correct
11 Correct 105 ms 35412 KB Output is correct
12 Correct 120 ms 35412 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 1880 KB Output is correct
7 Correct 2 ms 1884 KB Output is correct
8 Correct 18 ms 14012 KB Output is correct
9 Correct 20 ms 14396 KB Output is correct
10 Correct 17 ms 13840 KB Output is correct
11 Correct 233 ms 36148 KB Output is correct
12 Correct 232 ms 35664 KB Output is correct
13 Correct 274 ms 36304 KB Output is correct
14 Correct 329 ms 46676 KB Output is correct
15 Correct 342 ms 50824 KB Output is correct
16 Correct 105 ms 35412 KB Output is correct
17 Correct 120 ms 35412 KB Output is correct
18 Correct 616 ms 225884 KB Output is correct
19 Correct 654 ms 234672 KB Output is correct
20 Correct 998 ms 380256 KB Output is correct
21 Correct 509 ms 199248 KB Output is correct
22 Correct 143 ms 39256 KB Output is correct
23 Correct 135 ms 39616 KB Output is correct
24 Correct 640 ms 216656 KB Output is correct