oj.uz

Submission #275665

# Submission time Handle Problem Language Result Execution time Memory
275665 2020-08-20T06:59:21 Z 최은수(#5098) Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 2000 ms 436112 KB 
#include"happiness.h"
#include<iostream>
#include<vector>
#include<unordered_map>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
struct seg
{
	struct node
	{
		ll v,lz;
		node*l,*r;
		node(){v=lz=0,l=r=nullptr;}
	};
	node*rt;
	seg(){rt=nullptr;}
	void upd(node*&n,ll s,ll e,ll S,ll E,ll p)
	{
		if(s>E||S>e)
			return;
		if(n==nullptr)
			n=new node();
		if(S<=s&&e<=E)
		{
			n->v+=p;
			n->lz+=p;
			return;
		}
		ll m=s+(e-s)/2;
		upd(n->l,s,m,S,E,p);
		upd(n->r,m+1,e,S,E,p);
		n->v=min(n->l==nullptr?0:n->l->v,n->r==nullptr?0:n->r->v)+n->lz;
		return;
	}
}st;
ll m;
unordered_map<ll,int>mp;
bool init(int coinsCount,ll maxCoinSize,ll coins[])
{
	m=maxCoinSize;
	st.upd(st.rt,1,m,1,m,0);
	int n=coinsCount;
	for(int i=0;i<n;i++)
	{
		ll t=coins[i];
		if(mp[t]++==0)
			st.upd(st.rt,1,m,t,t,-t);
		if(t<m)
			st.upd(st.rt,1,m,t+1,m,t);
	}
	return st.rt->v>=-1;
}
bool is_happy(int event,int coinsCount,ll coins[])
{
	int n=coinsCount;
	if(event==1)
	{
		for(int i=0;i<n;i++)
		{
			ll t=coins[i];
			if(mp[t]++==0)
				st.upd(st.rt,1,m,t,t,-t);
			if(t<m)
				st.upd(st.rt,1,m,t+1,m,t);
		}
	}
	else
	{
		for(int i=0;i<n;i++)
		{
			ll t=coins[i];
			if(--mp[t]==0)
				st.upd(st.rt,1,m,t,t,t);
			if(t<m)
				st.upd(st.rt,1,m,t+1,m,-t);
		}
	}
	return st.rt->v>=-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;
      |            ^~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 7 ms 2560 KB Output is correct
7 Correct 6 ms 2816 KB Output is correct
8 Correct 69 ms 20740 KB Output is correct
9 Correct 59 ms 20984 KB Output is correct
10 Correct 58 ms 20216 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 814 ms 50676 KB Output is correct
7 Correct 809 ms 49896 KB Output is correct
8 Correct 872 ms 50756 KB Output is correct
9 Correct 1346 ms 66696 KB Output is correct
10 Correct 1298 ms 71396 KB Output is correct
11 Correct 524 ms 48508 KB Output is correct
12 Correct 494 ms 48356 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 7 ms 2560 KB Output is correct
7 Correct 6 ms 2816 KB Output is correct
8 Correct 69 ms 20740 KB Output is correct
9 Correct 59 ms 20984 KB Output is correct
10 Correct 58 ms 20216 KB Output is correct
11 Correct 814 ms 50676 KB Output is correct
12 Correct 809 ms 49896 KB Output is correct
13 Correct 872 ms 50756 KB Output is correct
14 Correct 1346 ms 66696 KB Output is correct
15 Correct 1298 ms 71396 KB Output is correct
16 Correct 524 ms 48508 KB Output is correct
17 Correct 494 ms 48356 KB Output is correct
18 Correct 1787 ms 330172 KB Output is correct
19 Correct 1781 ms 343356 KB Output is correct
20 Execution timed out 2110 ms 436112 KB Time limit exceeded
21 Halted 0 ms 0 KB -