| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1086911 | serifefedartar | Happiness (Balkan15_HAPPINESS) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "happiness.h"
#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0)
typedef long long ll;
#define f first
#define s second
#define LOGN 21
const ll MOD = 1e9 + 7;
const ll MAXN = 1e6 + 100;
struct Node {
int l, r;
int sum;
Node *ln, *rn;
Node(int _l, int _r) : l(_l), r(_r), sum(0), ln(NULL), rn(NULL) { }
int query(int a, int b) {
if (r < a || l > b)
return 0;
if (l <= a && b <= r)
return sum;
int res = 0;
if (ln)
res += ln->query(a, b);
if (rn)
res += rn->query(a, b);
return res;
}
void update(int plc, int val) {
sum += val;
if (l != r) {
int mid = (l + r) / 2;
if (plc > mid) {
if (!rn)
rn = new Node(mid + 1, r);
rn->update(plc, val);
} else {
if (!ln)
ln = new Node(l, mid);
ln->update(plc, val);
}
}
}
};
Node *root;
bool solve() {
int now = 1;
while (now < root->sum) {
int t = root->query(1, now);
if (t < now)
return false;
now = t + 1;
}
return true;
}
bool init(int coinsCount, int maxCoinSize, int coins[]) {
root = new Node(1, maxCoinSize);
root->update(1, 1);
for (int i = 0; i < coinsCount; i++)
root->update(coins[i], coins[i]);
return solve();
}
bool is_happy(int event, int coinsCount, int coins[]) {
for (int i = 0; i < coinsCount; i++)
root->update(coins[i], event * coins[i]);
return solve();
}