Submission #1278835

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278835		Robert_junior	Happiness (Balkan15_HAPPINESS)	C++20	10 / 100	340 ms	9612 KiB

happiness

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

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