oj.uz

Submission #275676

# Submission time Handle Problem Language Result Execution time Memory
275676 2020-08-20T07:02:10 Z 최은수(#5098) Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 1315 ms 303152 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[6000010];
	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 84 ms 141176 KB Output is correct
2 Correct 91 ms 141304 KB Output is correct
3 Correct 86 ms 141176 KB Output is correct
4 Correct 84 ms 141176 KB Output is correct
5 Correct 85 ms 141176 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 141176 KB Output is correct
2 Correct 91 ms 141304 KB Output is correct
3 Correct 86 ms 141176 KB Output is correct
4 Correct 84 ms 141176 KB Output is correct
5 Correct 85 ms 141176 KB Output is correct
6 Correct 88 ms 141304 KB Output is correct
7 Correct 99 ms 141304 KB Output is correct
8 Correct 132 ms 141688 KB Output is correct
9 Correct 139 ms 141816 KB Output is correct
10 Correct 116 ms 141688 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 141176 KB Output is correct
2 Correct 91 ms 141304 KB Output is correct
3 Correct 86 ms 141176 KB Output is correct
4 Correct 84 ms 141176 KB Output is correct
5 Correct 85 ms 141176 KB Output is correct
6 Correct 769 ms 149992 KB Output is correct
7 Correct 776 ms 149836 KB Output is correct
8 Correct 784 ms 149952 KB Output is correct
9 Correct 1154 ms 156352 KB Output is correct
10 Correct 1220 ms 156224 KB Output is correct
11 Correct 542 ms 156500 KB Output is correct
12 Correct 537 ms 156492 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 141176 KB Output is correct
2 Correct 91 ms 141304 KB Output is correct
3 Correct 86 ms 141176 KB Output is correct
4 Correct 84 ms 141176 KB Output is correct
5 Correct 85 ms 141176 KB Output is correct
6 Correct 88 ms 141304 KB Output is correct
7 Correct 99 ms 141304 KB Output is correct
8 Correct 132 ms 141688 KB Output is correct
9 Correct 139 ms 141816 KB Output is correct
10 Correct 116 ms 141688 KB Output is correct
11 Correct 769 ms 149992 KB Output is correct
12 Correct 776 ms 149836 KB Output is correct
13 Correct 784 ms 149952 KB Output is correct
14 Correct 1154 ms 156352 KB Output is correct
15 Correct 1220 ms 156224 KB Output is correct
16 Correct 542 ms 156500 KB Output is correct
17 Correct 537 ms 156492 KB Output is correct
18 Runtime error 1315 ms 303152 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -