oj.uz

Submission #275678

# Submission time Handle Problem Language Result Execution time Memory
275678 2020-08-20T07:03:13 Z 최은수(#5098) Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 2000 ms 298276 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;
		int l,r;
		node(){v=lz=0,l=r=0;}
	}st[12000010];
	int tct;
	int rt;
	seg(){rt=tct=0;}
	void upd(int&n,ll s,ll e,ll S,ll E,ll p)
	{
		if(n==0)
			n=++tct;
		if(S<=s&&e<=E)
		{
			st[n].v+=p;
			st[n].lz+=p;
			return;
		}
		ll m=s+(e-s)/2;
		if(S<=m)
			upd(st[n].l,s,m,S,E,p);
		if(E>m)
			upd(st[n].r,m+1,e,S,E,p);
		st[n].v=min(st[st[n].l].v,st[st[n].r].v)+st[n].lz;
		return;
	}
}st;
ll m;
unordered_map<ll,int>mp;
bool init(int coinsCount,ll maxCoinSize,ll coins[])
{
	m=maxCoinSize;
	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.st[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.st[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 171 ms 282104 KB Output is correct
2 Correct 193 ms 282136 KB Output is correct
3 Correct 171 ms 282104 KB Output is correct
4 Correct 173 ms 282220 KB Output is correct
5 Correct 179 ms 282108 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 282104 KB Output is correct
2 Correct 193 ms 282136 KB Output is correct
3 Correct 171 ms 282104 KB Output is correct
4 Correct 173 ms 282220 KB Output is correct
5 Correct 179 ms 282108 KB Output is correct
6 Correct 176 ms 282152 KB Output is correct
7 Correct 180 ms 282108 KB Output is correct
8 Correct 218 ms 282616 KB Output is correct
9 Correct 246 ms 282616 KB Output is correct
10 Correct 215 ms 282744 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 282104 KB Output is correct
2 Correct 193 ms 282136 KB Output is correct
3 Correct 171 ms 282104 KB Output is correct
4 Correct 173 ms 282220 KB Output is correct
5 Correct 179 ms 282108 KB Output is correct
6 Correct 884 ms 291004 KB Output is correct
7 Correct 829 ms 290716 KB Output is correct
8 Correct 950 ms 290832 KB Output is correct
9 Correct 1335 ms 297208 KB Output is correct
10 Correct 1327 ms 297240 KB Output is correct
11 Correct 615 ms 297444 KB Output is correct
12 Correct 628 ms 297556 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 282104 KB Output is correct
2 Correct 193 ms 282136 KB Output is correct
3 Correct 171 ms 282104 KB Output is correct
4 Correct 173 ms 282220 KB Output is correct
5 Correct 179 ms 282108 KB Output is correct
6 Correct 176 ms 282152 KB Output is correct
7 Correct 180 ms 282108 KB Output is correct
8 Correct 218 ms 282616 KB Output is correct
9 Correct 246 ms 282616 KB Output is correct
10 Correct 215 ms 282744 KB Output is correct
11 Correct 884 ms 291004 KB Output is correct
12 Correct 829 ms 290716 KB Output is correct
13 Correct 950 ms 290832 KB Output is correct
14 Correct 1335 ms 297208 KB Output is correct
15 Correct 1327 ms 297240 KB Output is correct
16 Correct 615 ms 297444 KB Output is correct
17 Correct 628 ms 297556 KB Output is correct
18 Correct 1453 ms 291652 KB Output is correct
19 Correct 1433 ms 291900 KB Output is correct
20 Execution timed out 2029 ms 298276 KB Time limit exceeded
21 Halted 0 ms 0 KB -