oj.uz

Submission #275692

# Submission time Handle Problem Language Result Execution time Memory
275692 2020-08-20T07:08:20 Z 최은수(#5098) Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 2000 ms 505188 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[10000010];
	int tct;
	int rt;
	seg(){rt=tct=0;}
	void upd(int&n,const ll&s,const ll&e,const ll&S,const ll&E,const 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 149 ms 235256 KB Output is correct
2 Correct 140 ms 235128 KB Output is correct
3 Correct 142 ms 235128 KB Output is correct
4 Correct 154 ms 235096 KB Output is correct
5 Correct 155 ms 235256 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 235256 KB Output is correct
2 Correct 140 ms 235128 KB Output is correct
3 Correct 142 ms 235128 KB Output is correct
4 Correct 154 ms 235096 KB Output is correct
5 Correct 155 ms 235256 KB Output is correct
6 Correct 163 ms 235160 KB Output is correct
7 Correct 146 ms 235256 KB Output is correct
8 Correct 178 ms 235720 KB Output is correct
9 Correct 185 ms 235672 KB Output is correct
10 Correct 176 ms 235668 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 235256 KB Output is correct
2 Correct 140 ms 235128 KB Output is correct
3 Correct 142 ms 235128 KB Output is correct
4 Correct 154 ms 235096 KB Output is correct
5 Correct 155 ms 235256 KB Output is correct
6 Correct 977 ms 243764 KB Output is correct
7 Correct 820 ms 243860 KB Output is correct
8 Correct 971 ms 243900 KB Output is correct
9 Correct 1371 ms 250172 KB Output is correct
10 Correct 1280 ms 250172 KB Output is correct
11 Correct 647 ms 250472 KB Output is correct
12 Correct 632 ms 250488 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 235256 KB Output is correct
2 Correct 140 ms 235128 KB Output is correct
3 Correct 142 ms 235128 KB Output is correct
4 Correct 154 ms 235096 KB Output is correct
5 Correct 155 ms 235256 KB Output is correct
6 Correct 163 ms 235160 KB Output is correct
7 Correct 146 ms 235256 KB Output is correct
8 Correct 178 ms 235720 KB Output is correct
9 Correct 185 ms 235672 KB Output is correct
10 Correct 176 ms 235668 KB Output is correct
11 Correct 977 ms 243764 KB Output is correct
12 Correct 820 ms 243860 KB Output is correct
13 Correct 971 ms 243900 KB Output is correct
14 Correct 1371 ms 250172 KB Output is correct
15 Correct 1280 ms 250172 KB Output is correct
16 Correct 647 ms 250472 KB Output is correct
17 Correct 632 ms 250488 KB Output is correct
18 Correct 1572 ms 244544 KB Output is correct
19 Correct 1530 ms 244708 KB Output is correct
20 Execution timed out 2115 ms 505188 KB Time limit exceeded
21 Halted 0 ms 0 KB -