#include "happiness.h"
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
#define N fhq[n]
random_device rd;
mt19937_64 rng(0);
int tots, cnt;
//gp_hash_table<long long,long long> bit;
unordered_map<long long, long long> bit;
struct node {
uint64_t key;
int64_t lz,dif,val,cnt,mx;
int l, r;
} fhq[1000100];
int root;
int nn(int val, int dif) {
fhq[++cnt]={rng(),0,dif,val,1,dif,0,0};
return cnt;
}
void pd(int n) {
if(N.lz) {
fhq[N.l].lz+=N.lz;
fhq[N.r].lz+=N.lz;
N.dif+=N.lz;
N.mx+=N.lz;
N.lz=0;
}
}
void PU(int n) {
N.mx=N.dif;
if(N.l)
N.mx=max(fhq[N.l].mx,N.mx);
if(N.r)
N.mx=max(fhq[N.r].mx,N.mx);
}
void merge(int &n, int l, int r) {
if(!l||!r) return void(n=l+r);
pd(l),pd(r);
if(fhq[l].key<fhq[r].key)
merge(fhq[r].l, l,fhq[r].l),n=r;
else merge(fhq[l].r,fhq[l].r,r),n=l;
PU(n);
}
void split(int n, int &l, int &r, long long val) {
if(!n)return void(l=r=0); pd(n);
if(N.val<=val) split(N.r,N.r,r,val),l=n;
else split(N.l,l,N.l,val),r=n;
PU(n);
}
int find(int n, long long target) {
if(!n)return n;
if(N.val==target)return n;
if(N.val>target)
return find(N.l,target);
return find(N.r,target);
}
void upd(long long pos, long long v) {
int x, y;
split(root,x,y,pos);
fhq[y].lz+=v;
merge(root,x,y);
for(;pos<=1e12;pos+=pos&-pos)
bit[pos]+=v;
}
void ins(long long val) {
upd(val,-val);
int x = find(root,val),y,z;
if(x) fhq[x].cnt++;
else {
split(root,x,y,val);
long long ch = 0;
for(long long x = val-1; x; x-=x&-x)
ch+=bit[x];
z = nn(val,val+ch);
merge(root,x,z);
merge(root,root,y);
}
}
void del(long long val) {
upd(val,val);
int x = find(root,val),y,z;
if(fhq[x].cnt>1) fhq[x].cnt--;
else {
split(root,x,y,val-1);
split(y,y,z,val);
merge(root,x,z);
}
}
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
root=nn(*coins,*coins);
upd(*coins,-*coins);
for(int i = 1; i < coinsCount; i++)
ins(coins[i]);
return fhq[root].mx<2;
}
bool is_happy(int event, int coinsCount, long long coins[]) {
for(int i = 0; i < coinsCount; i++)
(event+1?ins:del)(coins[i]);
return fhq[root].mx<2;
}
Compilation message
happiness.cpp: In function 'void split(int, int&, int&, long long int)':
happiness.cpp:47:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
47 | if(!n)return void(l=r=0); pd(n);
| ^~
happiness.cpp:47:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
47 | if(!n)return void(l=r=0); pd(n);
| ^~
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 |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
