oj.uz

Submission #343957

# Submission time Handle Problem Language Result Execution time Memory
343957 2021-01-04T22:19:00 Z ogibogi2004 Happiness (Balkan15_HAPPINESS) C++14
100 / 100
 1599 ms 244588 KB 
#include "happiness.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXM=1e7;
const ll INF=2e17;
const ll MAXN=2e12;
struct node
{
	ll val;
	ll pl,pr;
	node()
	{
		val=0;pl=-1;pr=-1;
	}
};
node tree[MAXM];
ll sz=1;
void update(ll 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;
}
ll query(ll 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(ll 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(ll i=0;i<coinsCount;i++)
		{
			update(1,1,MAXN,coins[i],coins[i]);
		}
	}
	else
	{
		for(ll 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

# Verdict Execution time Memory Grader output
1 Correct 141 ms 235116 KB Output is correct
2 Correct 127 ms 235116 KB Output is correct
3 Correct 127 ms 235116 KB Output is correct
4 Correct 128 ms 235244 KB Output is correct
5 Correct 125 ms 235116 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 235116 KB Output is correct
2 Correct 127 ms 235116 KB Output is correct
3 Correct 127 ms 235116 KB Output is correct
4 Correct 128 ms 235244 KB Output is correct
5 Correct 125 ms 235116 KB Output is correct
6 Correct 127 ms 235244 KB Output is correct
7 Correct 131 ms 235244 KB Output is correct
8 Correct 147 ms 235500 KB Output is correct
9 Correct 146 ms 235372 KB Output is correct
10 Correct 145 ms 235500 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 235116 KB Output is correct
2 Correct 127 ms 235116 KB Output is correct
3 Correct 127 ms 235116 KB Output is correct
4 Correct 128 ms 235244 KB Output is correct
5 Correct 125 ms 235116 KB Output is correct
6 Correct 857 ms 236268 KB Output is correct
7 Correct 862 ms 239456 KB Output is correct
8 Correct 940 ms 239468 KB Output is correct
9 Correct 1148 ms 241260 KB Output is correct
10 Correct 1120 ms 240872 KB Output is correct
11 Correct 497 ms 239212 KB Output is correct
12 Correct 473 ms 239332 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 235116 KB Output is correct
2 Correct 127 ms 235116 KB Output is correct
3 Correct 127 ms 235116 KB Output is correct
4 Correct 128 ms 235244 KB Output is correct
5 Correct 125 ms 235116 KB Output is correct
6 Correct 127 ms 235244 KB Output is correct
7 Correct 131 ms 235244 KB Output is correct
8 Correct 147 ms 235500 KB Output is correct
9 Correct 146 ms 235372 KB Output is correct
10 Correct 145 ms 235500 KB Output is correct
11 Correct 857 ms 236268 KB Output is correct
12 Correct 862 ms 239456 KB Output is correct
13 Correct 940 ms 239468 KB Output is correct
14 Correct 1148 ms 241260 KB Output is correct
15 Correct 1120 ms 240872 KB Output is correct
16 Correct 497 ms 239212 KB Output is correct
17 Correct 473 ms 239332 KB Output is correct
18 Correct 1188 ms 241656 KB Output is correct
19 Correct 1212 ms 241828 KB Output is correct
20 Correct 1599 ms 244588 KB Output is correct
21 Correct 898 ms 241004 KB Output is correct
22 Correct 487 ms 241132 KB Output is correct
23 Correct 488 ms 241644 KB Output is correct
24 Correct 1160 ms 241684 KB Output is correct