Submission #282869

#	Time	Username	Problem	Language	Result	Execution time	Memory
282869		imeimi2000	Happiness (Balkan15_HAPPINESS)	C++17	100 / 100	1144 ms	398476 KiB

happiness

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40