oj.uz

Submission #275708

# Submission time Handle Problem Language Result Execution time Memory
275708 2020-08-20T07:15:18 Z 최은수(#5098) Happiness (Balkan15_HAPPINESS) C++17
100 / 100
 1891 ms 353892 KB 
#include"happiness.h"
#include<iostream>
#include<vector>
#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[15000010];
	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;
			if(s<e)
				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;
	}
	void upd2(int&n,const ll&s,const ll&e,const ll&x)
	{
		if(n==0)
			n=++tct;
		if(s==e)
		{
			if(st[n].lz++==0)
				st[n].v-=x;
			return;
		}
		ll m=s+(e-s)/2;
		if(x>m)
			upd2(st[n].r,m+1,e,x);
		else
			upd2(st[n].l,s,m,x);
		st[n].v=min(st[st[n].l].v,st[st[n].r].v)+st[n].lz;
		return;
	}
	void upd3(int&n,const ll&s,const ll&e,const ll&x)
	{
		if(n==0)
			n=++tct;
		if(s==e)
		{
			if(--st[n].lz==0)
				st[n].v+=x;
			return;
		}
		ll m=s+(e-s)/2;
		if(x>m)
			upd3(st[n].r,m+1,e,x);
		else
			upd3(st[n].l,s,m,x);
		st[n].v=min(st[st[n].l].v,st[st[n].r].v)+st[n].lz;
		return;
	}
}st;
ll m;
bool init(int coinsCount,ll maxCoinSize,ll coins[])
{
	m=maxCoinSize;
	int n=coinsCount;
	for(int i=0;i<n;i++)
	{
		ll t=coins[i];
		st.upd2(st.rt,1,m,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];
			st.upd2(st.rt,1,m,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];
			st.upd3(st.rt,1,m,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 212 ms 352504 KB Output is correct
2 Correct 224 ms 352504 KB Output is correct
3 Correct 210 ms 352504 KB Output is correct
4 Correct 214 ms 352504 KB Output is correct
5 Correct 214 ms 352632 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 352504 KB Output is correct
2 Correct 224 ms 352504 KB Output is correct
3 Correct 210 ms 352504 KB Output is correct
4 Correct 214 ms 352504 KB Output is correct
5 Correct 214 ms 352632 KB Output is correct
6 Correct 222 ms 352524 KB Output is correct
7 Correct 220 ms 352504 KB Output is correct
8 Correct 242 ms 352632 KB Output is correct
9 Correct 263 ms 352696 KB Output is correct
10 Correct 251 ms 352892 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 352504 KB Output is correct
2 Correct 224 ms 352504 KB Output is correct
3 Correct 210 ms 352504 KB Output is correct
4 Correct 214 ms 352504 KB Output is correct
5 Correct 214 ms 352632 KB Output is correct
6 Correct 780 ms 353892 KB Output is correct
7 Correct 770 ms 353528 KB Output is correct
8 Correct 756 ms 353540 KB Output is correct
9 Correct 1143 ms 353692 KB Output is correct
10 Correct 1119 ms 353716 KB Output is correct
11 Correct 684 ms 352760 KB Output is correct
12 Correct 727 ms 352908 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 352504 KB Output is correct
2 Correct 224 ms 352504 KB Output is correct
3 Correct 210 ms 352504 KB Output is correct
4 Correct 214 ms 352504 KB Output is correct
5 Correct 214 ms 352632 KB Output is correct
6 Correct 222 ms 352524 KB Output is correct
7 Correct 220 ms 352504 KB Output is correct
8 Correct 242 ms 352632 KB Output is correct
9 Correct 263 ms 352696 KB Output is correct
10 Correct 251 ms 352892 KB Output is correct
11 Correct 780 ms 353892 KB Output is correct
12 Correct 770 ms 353528 KB Output is correct
13 Correct 756 ms 353540 KB Output is correct
14 Correct 1143 ms 353692 KB Output is correct
15 Correct 1119 ms 353716 KB Output is correct
16 Correct 684 ms 352760 KB Output is correct
17 Correct 727 ms 352908 KB Output is correct
18 Correct 1411 ms 353560 KB Output is correct
19 Correct 1388 ms 353528 KB Output is correct
20 Correct 1891 ms 353656 KB Output is correct
21 Correct 1228 ms 353644 KB Output is correct
22 Correct 1129 ms 352880 KB Output is correct
23 Correct 1067 ms 352748 KB Output is correct
24 Correct 1323 ms 353528 KB Output is correct