Submission #1278838

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278838		Robert_junior	Happiness (Balkan15_HAPPINESS)	C++20	100 / 100	1590 ms	187000 KiB

happiness

#include "happiness.h"
#include <bits/stdc++.h>
using namespace std;
const long long N = 2e5 + 7;
long long inf = 1e13;
long long t[N * 40], L[N * 40], R[N * 40], timer = 1;
void upd(long long v, long long l, long long r, long long idx, long long x){
    if(l == r){
        t[v] += x;
    }
    else{
        long long m = (l + r) / 2;
        if(idx <= m){
            if(!L[v]) L[v] = ++timer;
            upd(L[v], l, m, idx, x);
        }
        else{
            if(!R[v]) R[v] = ++timer;
            upd(R[v], m + 1, r, idx, x);
        }
        t[v] = t[L[v]] + t[R[v]];
    }
}
long long get(long long v, long long l, long long r, long long ll, long long rr){
    if(l <= ll && rr <= r) return t[v];
    if(l > rr || ll > r) return 0;
    long long m = (ll + rr) / 2;
    return get(L[v], l, r, ll, m) + get(R[v], l, r, m + 1, rr);
}
bool check(){
    long long cur = 1, sum = t[1]; 
    while(cur < sum){
        long long t = get(1, 1, cur, 1, inf);
        if(t < cur) return false;
        cur = t + 1;
    }
    return true;
}
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
    for(long long i = 0; i < coinsCount; i++){
        upd(1, 1, inf, coins[i], coins[i]);
    }
    return check();
}
bool is_happy(int event, int coinsCount, long long coins[]) {
    for(long long i = 0; i < coinsCount; i++){
        upd(1, 1, inf, coins[i], event * coins[i]);
    }
    return check();
}

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