oj.uz

Submission #275604

# Submission time Handle Problem Language Result Execution time Memory
275604 2020-08-20T06:44:08 Z 최은수(#5098) Happiness (Balkan15_HAPPINESS) C++17
40 / 100
 1829 ms 524288 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[6000010];
	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;
		}
		int 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[1].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[1].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 87 ms 141176 KB Output is correct
2 Correct 86 ms 141176 KB Output is correct
3 Correct 100 ms 141176 KB Output is correct
4 Correct 93 ms 141176 KB Output is correct
5 Correct 86 ms 141176 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 141176 KB Output is correct
2 Correct 86 ms 141176 KB Output is correct
3 Correct 100 ms 141176 KB Output is correct
4 Correct 93 ms 141176 KB Output is correct
5 Correct 86 ms 141176 KB Output is correct
6 Runtime error 343 ms 524288 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 141176 KB Output is correct
2 Correct 86 ms 141176 KB Output is correct
3 Correct 100 ms 141176 KB Output is correct
4 Correct 93 ms 141176 KB Output is correct
5 Correct 86 ms 141176 KB Output is correct
6 Correct 1055 ms 153464 KB Output is correct
7 Correct 994 ms 153336 KB Output is correct
8 Correct 1063 ms 153592 KB Output is correct
9 Correct 1803 ms 158796 KB Output is correct
10 Correct 1829 ms 161288 KB Output is correct
11 Correct 831 ms 163320 KB Output is correct
12 Correct 792 ms 163368 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 141176 KB Output is correct
2 Correct 86 ms 141176 KB Output is correct
3 Correct 100 ms 141176 KB Output is correct
4 Correct 93 ms 141176 KB Output is correct
5 Correct 86 ms 141176 KB Output is correct
6 Runtime error 343 ms 524288 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -