#include "happiness.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXM=1e7;
const ll INF=2e17;
const ll MAXN=2e12;
struct node
{
int pl,pr;
ll val;
ll ans;
int cnt;
ll lazy;
node()
{
pl=-1;pr=-1;
cnt=0;val=0;
lazy=0;
}
};
node tree[MAXM];
int sz=1;
void create_children(int idx,ll l,ll r)
{
ll mid=(l+r)/2;
if(tree[idx].pl==-1)
{
tree[idx].pl=++sz;
if(l==mid)tree[tree[idx].pl].val+=l;
}
if(tree[idx].pr==-1)
{
tree[idx].pr=++sz;
if(mid+1==r)tree[tree[idx].pr].val+=r;
}
}
void push(int idx,ll l,ll r)
{
if(tree[idx].lazy==0)
{
return;
}
tree[idx].val+=tree[idx].lazy;
if(tree[idx].ans!=-INF)tree[idx].ans+=tree[idx].lazy;
if(l!=r)
{
create_children(idx,l,r);
tree[tree[idx].pl].lazy+=tree[idx].lazy;
tree[tree[idx].pr].lazy+=tree[idx].lazy;
}
tree[idx].lazy=0;
}
void upd1(int idx,ll l,ll r,ll q,ll val)
{
push(idx,l,r);
if(r<q)return;
if(l>q)return;
//push(idx,l,r);
if(l==r)
{
tree[idx].cnt+=val;
if(tree[idx].cnt==0)
{
tree[idx].ans=-INF;
}
else tree[idx].ans=tree[idx].val;
//if(tree[idx].ans!=-INF)cout<<l<<" "<<r<<" "<<tree[idx].ans<<endl;
return;
}
create_children(idx,l,r);
ll mid=(l+r)/2;
upd1(tree[idx].pl,l,mid,q,val);
upd1(tree[idx].pr,mid+1,r,q,val);
tree[idx].cnt=tree[tree[idx].pl].cnt+tree[tree[idx].pr].cnt;
tree[idx].ans=max(tree[tree[idx].pl].ans,tree[tree[idx].pr].ans);
if(tree[idx].cnt==0)tree[idx].ans=-INF;
//if(tree[idx].ans!=-INF)cout<<l<<" "<<r<<" "<<tree[idx].ans<<endl;
}
void upd2(int idx,ll l,ll r,ll ql,ll qr,ll val)
{
push(idx,l,r);
if(l>qr)return;
if(r<ql)return;
if(l>=ql&&r<=qr)
{
tree[idx].lazy+=val;
if(tree[idx].ans!=-INF)tree[idx].ans+=val;
else tree[idx].ans=-INF;
push(idx,l,r);
//if(tree[idx].ans!=-INF)cout<<l<<" "<<r<<" "<<tree[idx].ans<<endl;
return;
}
ll mid=(l+r)/2;
upd2(tree[idx].pl,l,mid,ql,qr,val);
upd2(tree[idx].pr,mid+1,r,ql,qr,val);
tree[idx].cnt=tree[tree[idx].pl].cnt+tree[tree[idx].pr].cnt;
tree[idx].ans=max(tree[tree[idx].pl].ans,tree[tree[idx].pr].ans);
if(tree[idx].cnt==0)tree[idx].ans=-INF;
//if(tree[idx].ans!=-INF)cout<<l<<" "<<r<<" "<<tree[idx].ans<<endl;
}
void print(int idx,ll l,ll r)
{
cout<<l<<" "<<r<<" "<<tree[idx].ans<<" "<<tree[idx].lazy<<endl;
if(tree[idx].pl!=-1)print(tree[idx].pl,l,(l+r)/2);
if(tree[idx].pr!=-1)print(tree[idx].pr,(l+r)/2+1,r);
}
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
tree[1].ans=INF;
//sort(coins,coins+coinsCount);
for(int i=0;i<coinsCount;i++)
{
upd1(1,1,MAXN,coins[i],+1);
upd2(1,1,MAXN,coins[i]+1,MAXN,-coins[i]);
//print(1,1,MAXN);
//cout<<coins[i]<<" --------\n";
}
//cout<<tree[1].ans<<endl;
push(1,1,MAXN);
if(tree[1].ans>1)return 0;
else return 1;
}
bool is_happy(int event, int coinsCount, long long coins[]) {
if(event==-1)
{
for(int i=0;i<coinsCount;i++)
{
upd1(1,1,MAXN,coins[i],-1);
upd2(1,1,MAXN,coins[i]+1,MAXN,+coins[i]);
//print(1,1,MAXN);
}
}
else
{
for(int i=0;i<coinsCount;i++)
{
upd1(1,1,MAXN,coins[i],+1);
upd2(1,1,MAXN,coins[i]+1,MAXN,-coins[i]);
}
//print(1,1,MAXN);
}
//cout<<tree[1].ans<<endl;
push(1,1,MAXN);
if(tree[1].ans>1)return 0;
else return 1;
}
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 |
207 ms |
391660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
207 ms |
391660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
207 ms |
391660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
207 ms |
391660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
