Submission #343951

#	Time	Username	Problem	Language	Result	Execution time	Memory
343951		ogibogi2004	Happiness (Balkan15_HAPPINESS)	C++14	0 / 100	207 ms	391660 KiB

happiness

#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 (stderr)

grader.cpp: In function 'int main()':
grader.cpp:16:12: warning: unused variable 'max_code' [-Wunused-variable]
   16 |  long long max_code;
      |            ^~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40