#include "happiness.h"
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
#define O fhq[n].mx=max(max(fhq[fhq[n].l].mx,fhq[fhq[n].r].mx),fhq[n].dif);
random_device rd;
mt19937_64 rng(rd());
int tots, cnt;
gp_hash_table<long long,long long> bit;
struct node {
uint64_t key;
int64_t lz,dif,val,cnt,mx,llz,rlz;
int l, r;
} fhq[2000100];
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(fhq[n].lz) {
fhq[fhq[n].l].lz+=fhq[n].lz;
fhq[fhq[n].r].lz+=fhq[n].lz;
fhq[n].dif+=fhq[n].lz;
fhq[n].mx+=fhq[n].lz;
fhq[n].lz=0;
}
}
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].r),n=r;
else merge(fhq[l].r,fhq[l].r,r),n=l;O
}
void split(int n, int &l, int &r, long long val) {
if(!n)return void(l=r=0); pd(n);
if(fhq[n].val<=val) split(fhq[n].r,fhq[n].r,r,val),l=n;
else split(fhq[n].l,l,fhq[n].l,val),r=n;O
}
int find(int n, long long target) {
if(!n)return n;
if(fhq[n].val==target)return n;
if(fhq[n].val<target)
return find(fhq[n].l,target);
return find(fhq[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);
split(y,y,z,val+1);
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:38:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
38 | if(!n)return void(l=r=0); pd(n);
| ^~
happiness.cpp:38:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
38 | 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 |
- |
