#include "happiness.h"
#include <bits/stdc++.h>
using std::min;
#define ll long long
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define per(i, b, a) for (int i = b; i >= a; --i)
const long long INF = 1e18 + 5;
struct Node {
ll v = 1;
ll lazy = 0;
Node *l = nullptr;
Node *r = nullptr;
};
struct Seg3 {
Node *root = new Node;
void apply(Node*cur, ll x) {
(cur->v) += x;
(cur->lazy) += x;
}
void flush(Node *cur, int l, int r) {
if ((cur->l) == nullptr) (cur->l) = new Node;
if ((cur->r) == nullptr) (cur->r) = new Node;
if (l!=r) {
apply((cur->l), (cur->lazy));
apply((cur->r), (cur->lazy));
}
(cur->lazy) = 0;
}
ll join(ll a, ll b) {
return {min(a, b)};
}
void update(Node *cur, int l, int r, int tl, int tr, ll x) {
if (tr < l || tl > r) return;
if (l>=tl && r <= tr) {
apply(cur, x);
return;
}
flush(cur,l,r);
int mid =(l+r)>>1;
update((cur->l),l,mid,tl,tr,x);
update((cur->r),mid+1,r,tl,tr,x);
(cur->v) = join((cur->l)->v,(cur->r)->v);
}
ll query(Node *cur, int l, int r, int tl, int tr) {
if (tr < l || tl > r) return INF;
flush(cur,l,r);
if (l >= tl && r <= tr) return (cur-> v);
int mid = (l+r)>>1;
return join(query((cur->r),mid+1,r, tl,tr), query((cur->l), l, mid, tl,tr));
}
} seg;
ll s = 0, cnt1 = 0, m;
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
m = maxCoinSize;
rep(i,0,coinsCount-1) {
int x = coins[i];
s+=x;
if (x==1) cnt1++;
seg.update(seg.root,1,m,x+1,m,x);
seg.update(seg.root,1,m,x,x,-x);
}
ll mn = seg.query(seg.root,1,m,1,min(m,s));
return (cnt1>0 && mn >= 0);
}
bool is_happy(int event, int coinsCount, long long coins[]) {
rep(i,0,coinsCount-1) {
int x = coins[i];
s += x*event;
if (x==1) cnt1+=event;
seg.update(seg.root,1,m,x+1,m,x*event);
seg.update(seg.root,1,m,x,x,-x*event);
}
ll mn = seg.query(seg.root,1,m,1,min(m,s));
return (cnt1>0 && mn >= 0);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |