| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1278837 | Robert_junior | Happiness (Balkan15_HAPPINESS) | C++20 | 0 ms | 0 KiB |
#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(long long 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(long long event, long long coinsCount, long long coins[]){
for(long long i = 0; i < coinsCount; i++){
upd(1, 1, inf, coins[i], event * coins[i]);
}
return check();
}