#include "happiness.h"
#include <bits/stdc++.h>
int64_t P,sgn;
struct node{
int64_t sum=0,need=0;
node*left=0,*right=0;
inline node(){}
inline void update(int64_t l,int64_t r){
if(l==r){
sum+=P*sgn;
if(sum)need=P-1;
return;
}
int64_t mid=(l+r)>>1;
if(P<=mid){
if(!left)left=new node;
left->update(l,mid);
}else{
if(!right)right=new node;
right->update(mid+1,r);
}
sum=0;
need=0;
if(left){
sum=left->sum;
need=left->need;
}
if(right){
sum+=right->sum;
if(left)need=std::max(need,right->need-left->sum);
else need=right->need;
}
}
inline bool query(int64_t r){
if(r==1){
if(sum)return 1;
return 0;
}
if(!left)return 0;
if(right&&left->sum<right->need){
return 0;
}
return left->query((1+r)>>1);
}
};
struct segtree{
int n;
node*root;
inline segtree(int n):n(n){
root=new node;
}
inline void update(int p,int s){
P=p,sgn=s;
root->update(1,n);
}
inline bool query(){
return root->query(n);
}
};
segtree*st;
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
st=new segtree(maxCoinSize);
for(int i=0;i<coinsCount;i++){
st->update(coins[i],1);
}
return st->query();
}
bool is_happy(int event, int coinsCount, long long coins[]) {
for(int i=0;i<coinsCount;i++){
st->update(coins[i],event);
}
return st->query();
}
Compilation message
grader.cpp: In function 'int main()':
grader.cpp:16:12: warning: unused variable 'max_code' [-Wunused-variable]
16 | long long max_code;
| ^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
