oj.uz

Submission #275643

# Submission time Handle Problem Language Result Execution time Memory
275643 2020-08-20T06:52:21 Z 최은수(#5098) Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 2000 ms 304212 KB 
#include"happiness.h"
#include<iostream>
#include<vector>
#include<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(s>E||S>e)
			return;
		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;
		upd(st[n].l,s,m,S,E,p);
		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;
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 169 ms 282108 KB Output is correct
2 Correct 173 ms 282104 KB Output is correct
3 Correct 170 ms 282104 KB Output is correct
4 Correct 171 ms 282104 KB Output is correct
5 Correct 170 ms 282104 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 282108 KB Output is correct
2 Correct 173 ms 282104 KB Output is correct
3 Correct 170 ms 282104 KB Output is correct
4 Correct 171 ms 282104 KB Output is correct
5 Correct 170 ms 282104 KB Output is correct
6 Correct 177 ms 282172 KB Output is correct
7 Correct 172 ms 282232 KB Output is correct
8 Correct 207 ms 282832 KB Output is correct
9 Correct 205 ms 283128 KB Output is correct
10 Correct 209 ms 282872 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 282108 KB Output is correct
2 Correct 173 ms 282104 KB Output is correct
3 Correct 170 ms 282104 KB Output is correct
4 Correct 171 ms 282104 KB Output is correct
5 Correct 170 ms 282104 KB Output is correct
6 Correct 1088 ms 294668 KB Output is correct
7 Correct 1121 ms 294264 KB Output is correct
8 Correct 1156 ms 294664 KB Output is correct
9 Correct 1724 ms 299804 KB Output is correct
10 Correct 1839 ms 302116 KB Output is correct
11 Correct 812 ms 304196 KB Output is correct
12 Correct 826 ms 304212 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 282108 KB Output is correct
2 Correct 173 ms 282104 KB Output is correct
3 Correct 170 ms 282104 KB Output is correct
4 Correct 171 ms 282104 KB Output is correct
5 Correct 170 ms 282104 KB Output is correct
6 Correct 177 ms 282172 KB Output is correct
7 Correct 172 ms 282232 KB Output is correct
8 Correct 207 ms 282832 KB Output is correct
9 Correct 205 ms 283128 KB Output is correct
10 Correct 209 ms 282872 KB Output is correct
11 Correct 1088 ms 294668 KB Output is correct
12 Correct 1121 ms 294264 KB Output is correct
13 Correct 1156 ms 294664 KB Output is correct
14 Correct 1724 ms 299804 KB Output is correct
15 Correct 1839 ms 302116 KB Output is correct
16 Correct 812 ms 304196 KB Output is correct
17 Correct 826 ms 304212 KB Output is correct
18 Correct 1941 ms 295784 KB Output is correct
19 Correct 1809 ms 297696 KB Output is correct
20 Execution timed out 2093 ms 300376 KB Time limit exceeded
21 Halted 0 ms 0 KB -