oj.uz

Submission #280478

# Submission time Handle Problem Language Result Execution time Memory
280478 2020-08-22T20:07:50 Z dolphingarlic Happiness (Balkan15_HAPPINESS) C++14
100 / 100
 1607 ms 380236 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 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 3 ms 1792 KB Output is correct
7 Correct 4 ms 2048 KB Output is correct
8 Correct 31 ms 14072 KB Output is correct
9 Correct 32 ms 14200 KB Output is correct
10 Correct 28 ms 13816 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 498 ms 37624 KB Output is correct
7 Correct 495 ms 37240 KB Output is correct
8 Correct 518 ms 37496 KB Output is correct
9 Correct 745 ms 48888 KB Output is correct
10 Correct 725 ms 52856 KB Output is correct
11 Correct 176 ms 37112 KB Output is correct
12 Correct 175 ms 37240 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 3 ms 1792 KB Output is correct
7 Correct 4 ms 2048 KB Output is correct
8 Correct 31 ms 14072 KB Output is correct
9 Correct 32 ms 14200 KB Output is correct
10 Correct 28 ms 13816 KB Output is correct
11 Correct 498 ms 37624 KB Output is correct
12 Correct 495 ms 37240 KB Output is correct
13 Correct 518 ms 37496 KB Output is correct
14 Correct 745 ms 48888 KB Output is correct
15 Correct 725 ms 52856 KB Output is correct
16 Correct 176 ms 37112 KB Output is correct
17 Correct 175 ms 37240 KB Output is correct
18 Correct 1126 ms 225912 KB Output is correct
19 Correct 1180 ms 234736 KB Output is correct
20 Correct 1607 ms 380236 KB Output is correct
21 Correct 867 ms 199324 KB Output is correct
22 Correct 222 ms 39288 KB Output is correct
23 Correct 224 ms 39672 KB Output is correct
24 Correct 1128 ms 216812 KB Output is correct