oj.uz

답안 #343955

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
343955 2021-01-04T22:16:36 Z ogibogi2004 Happiness (Balkan15_HAPPINESS) C++14
10 / 100
 809 ms 161176 KB 
#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
{
	ll val;
	int pl,pr;
	node()
	{
		val=0;pl=-1;pr=-1;
	}
};
node tree[MAXM];
int sz=1;
void update(int idx,ll l,ll r,ll q,ll val)
{
	if(l>q||r<q)return;
	if(l==r)
	{
		tree[idx].val+=val;
		return;
	}
	ll mid=(l+r)/2;
	if(mid<q)
	{
		if(tree[idx].pr==-1)
		{
			tree[idx].pr=++sz;
		}
		update(tree[idx].pr,mid+1,r,q,val);
	}
	else
	{
		if(tree[idx].pl==-1)
		{
			tree[idx].pl=++sz;
		}
		update(tree[idx].pl,l,mid,q,val);
	}
	tree[idx].val=0;
	if(tree[idx].pl!=-1)tree[idx].val+=tree[tree[idx].pl].val;
	if(tree[idx].pr!=-1)tree[idx].val+=tree[tree[idx].pr].val;
}
int query(int idx,ll l,ll r,ll ql,ll qr)
{
	if(l>qr||r<ql)return 0;
	if(l>=ql&&r<=qr)
	{
		return tree[idx].val;
	}
	ll mid=(l+r)/2;
	ll ret=0;
	if(tree[idx].pl!=-1)
	{
		ret+=query(tree[idx].pl,l,mid,ql,qr);
	}
	if(tree[idx].pr!=-1)
	{
		ret+=query(tree[idx].pr,mid+1,r,ql,qr);
	}
	return ret;
}
bool check()
{
	ll csum=1;
	while(csum<tree[1].val)
	{
		ll t=query(1,1,MAXN,1,csum);
		if(t<csum)return 0;
		csum=t+1;
	}
	return 1;
}
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
	for(int i=0;i<coinsCount;i++)
	{
		update(1,1,MAXN,coins[i],coins[i]);
	}
	return check();
}
bool is_happy(int event, int coinsCount, long long coins[]) {
	
	if(event==1)
	{
		for(int i=0;i<coinsCount;i++)
		{
			update(1,1,MAXN,coins[i],coins[i]);
		}
	}
	else
	{
		for(int i=0;i<coinsCount;i++)
		{
			update(1,1,MAXN,coins[i],-coins[i]);
		}
	}
	return check();
}

Compilation message

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

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 93 ms 156908 KB Output is correct
2 Correct 93 ms 156908 KB Output is correct
3 Correct 94 ms 156956 KB Output is correct
4 Correct 94 ms 156908 KB Output is correct
5 Correct 93 ms 156908 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 93 ms 156908 KB Output is correct
2 Correct 93 ms 156908 KB Output is correct
3 Correct 94 ms 156956 KB Output is correct
4 Correct 94 ms 156908 KB Output is correct
5 Correct 93 ms 156908 KB Output is correct
6 Incorrect 95 ms 156928 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 93 ms 156908 KB Output is correct
2 Correct 93 ms 156908 KB Output is correct
3 Correct 94 ms 156956 KB Output is correct
4 Correct 94 ms 156908 KB Output is correct
5 Correct 93 ms 156908 KB Output is correct
6 Incorrect 809 ms 161176 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 93 ms 156908 KB Output is correct
2 Correct 93 ms 156908 KB Output is correct
3 Correct 94 ms 156956 KB Output is correct
4 Correct 94 ms 156908 KB Output is correct
5 Correct 93 ms 156908 KB Output is correct
6 Incorrect 95 ms 156928 KB Output isn't correct
7 Halted 0 ms 0 KB -