Submission #1283640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283640		ryazimn	Happiness (Balkan15_HAPPINESS)	C++20	100 / 100	1174 ms	125020 KiB

happiness

// #include "happiness.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll A = 1e12 + 1, N = 7e5 + 1;
int n, tot = 1;
ll ma;
ll seg[N * 41];
int ls[N * 41], rs[N * 41];
void add(int x, ll st, ll ed, ll pos, ll val) {
    if (st == ed) {
        seg[x] += val;
        return;
    }
    ll mid = (st + ed) / 2;
    if (pos <= mid) {
        if (ls[x] == 0) {
            ls[x] = ++tot;
        }
        add(ls[x], st, mid, pos, val);
    } else {
        if (rs[x] == 0) {
            rs[x] = ++tot;
        }
        add(rs[x], mid + 1, ed, pos, val);
    }
    seg[x] = seg[ls[x]] + seg[rs[x]];
}
ll getSum(int x, ll st, ll ed, ll l, ll r) {
    if (st > r || ed < l || x == 0) {
        return 0;
    }
    if (l <= st && ed <= r) {
        return seg[x];
    }
    ll mid = (st + ed) / 2;
    return getSum(ls[x], st, mid, l, r) + getSum(rs[x], mid + 1, ed, l, r);
}
bool check() {
    ll cur = 1;
    while (cur < min(seg[1], ma)) {
        ll t = getSum(1, 1, ma, 1, cur);
        if (t + 1 <= cur) {
            return false;
        }
        cur = t + 1;
    }
    return true;
}
bool init(int coinsCount, long long maxCoinSize, long long c[]) {
    ma = maxCoinSize;
    n = coinsCount;
    for (int i = 0; i < n; i++) {
        add(1, 1, ma, c[i], c[i]);
    }
	return check();
}
bool is_happy(int event, int coinsCount, long long c[]) {
    for (int i = 0; i < coinsCount; i++) {
        add(1, 1, ma, c[i], c[i] * event);
    }
	return check();
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40