oj.uz

Submission #282869

# Submission time Handle Problem Language Result Execution time Memory
282869 2020-08-25T05:44:20 Z imeimi2000 Happiness (Balkan15_HAPPINESS) C++17
100 / 100
 1144 ms 398476 KB 
#include "happiness.h"
 
typedef long long llong;
 
llong mx;
struct node {
    int l, r;
    llong sum;
    node() : l(-1), r(-1), sum(0) {}
} ns[42 * 600000];
 
int _alloc() {
    static int tp = 0;
    return tp++;
}
 
void update(int &i, llong s, llong e, llong x, llong v) {
    if (i == -1) i = _alloc();
    ns[i].sum += v;
    if (s == e) return;
    llong m = (s + e) / 2;
    if (x <= m) update(ns[i].l, s, m, x, v);
    else update(ns[i].r, m + 1, e, x, v);
}
 
llong query(int &i, llong s, llong e, llong x) {
    if (i == -1) return 0;
    if (x < s) return 0;
    if (e <= x) return ns[i].sum;
    llong m = (s + e) / 2;
    return query(ns[i].l, s, m, x) + query(ns[i].r, m + 1, e, x);
}
 
int rt;
bool check() {
    llong sum = 0, pr = -1;
    while (pr != sum) sum = query(rt, 1, mx, (pr = sum) + 1);
    return sum == ns[rt].sum;
}
 
bool init(int coinsCount, llong maxCoinSize, llong coins[]) {
    rt = _alloc();
    mx = maxCoinSize;
    for (int i = 0; i < coinsCount; ++i)
        update(rt, 1, mx, coins[i], coins[i]);
    return check();
}
bool is_happy(int event, int coinsCount, llong coins[]) {
    for (int i = 0; i < coinsCount; ++i)
        update(rt, 1, mx, 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 219 ms 394872 KB Output is correct
2 Correct 229 ms 394872 KB Output is correct
3 Correct 240 ms 394872 KB Output is correct
4 Correct 218 ms 394876 KB Output is correct
5 Correct 225 ms 394872 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 394872 KB Output is correct
2 Correct 229 ms 394872 KB Output is correct
3 Correct 240 ms 394872 KB Output is correct
4 Correct 218 ms 394876 KB Output is correct
5 Correct 225 ms 394872 KB Output is correct
6 Correct 217 ms 394876 KB Output is correct
7 Correct 242 ms 394872 KB Output is correct
8 Correct 236 ms 395256 KB Output is correct
9 Correct 231 ms 395232 KB Output is correct
10 Correct 230 ms 395000 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 394872 KB Output is correct
2 Correct 229 ms 394872 KB Output is correct
3 Correct 240 ms 394872 KB Output is correct
4 Correct 218 ms 394876 KB Output is correct
5 Correct 225 ms 394872 KB Output is correct
6 Correct 562 ms 398220 KB Output is correct
7 Correct 567 ms 398468 KB Output is correct
8 Correct 583 ms 398400 KB Output is correct
9 Correct 723 ms 398328 KB Output is correct
10 Correct 681 ms 398328 KB Output is correct
11 Correct 370 ms 397628 KB Output is correct
12 Correct 370 ms 397432 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 394872 KB Output is correct
2 Correct 229 ms 394872 KB Output is correct
3 Correct 240 ms 394872 KB Output is correct
4 Correct 218 ms 394876 KB Output is correct
5 Correct 225 ms 394872 KB Output is correct
6 Correct 217 ms 394876 KB Output is correct
7 Correct 242 ms 394872 KB Output is correct
8 Correct 236 ms 395256 KB Output is correct
9 Correct 231 ms 395232 KB Output is correct
10 Correct 230 ms 395000 KB Output is correct
11 Correct 562 ms 398220 KB Output is correct
12 Correct 567 ms 398468 KB Output is correct
13 Correct 583 ms 398400 KB Output is correct
14 Correct 723 ms 398328 KB Output is correct
15 Correct 681 ms 398328 KB Output is correct
16 Correct 370 ms 397628 KB Output is correct
17 Correct 370 ms 397432 KB Output is correct
18 Correct 899 ms 398200 KB Output is correct
19 Correct 929 ms 398456 KB Output is correct
20 Correct 1144 ms 398328 KB Output is correct
21 Correct 780 ms 398200 KB Output is correct
22 Correct 422 ms 397432 KB Output is correct
23 Correct 437 ms 397560 KB Output is correct
24 Correct 906 ms 398476 KB Output is correct