oj.uz

답안 #275706

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
275706 2020-08-20T07:14:06 Z 최은수(#5098) Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 1933 ms 478044 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[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;
			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

# 결과 실행 시간 메모리 Grader output
1 Correct 152 ms 235140 KB Output is correct
2 Correct 164 ms 235128 KB Output is correct
3 Correct 156 ms 235128 KB Output is correct
4 Correct 156 ms 235128 KB Output is correct
5 Correct 141 ms 235128 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 152 ms 235140 KB Output is correct
2 Correct 164 ms 235128 KB Output is correct
3 Correct 156 ms 235128 KB Output is correct
4 Correct 156 ms 235128 KB Output is correct
5 Correct 141 ms 235128 KB Output is correct
6 Correct 139 ms 235128 KB Output is correct
7 Correct 141 ms 235128 KB Output is correct
8 Correct 176 ms 235384 KB Output is correct
9 Correct 175 ms 235256 KB Output is correct
10 Correct 176 ms 235256 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 152 ms 235140 KB Output is correct
2 Correct 164 ms 235128 KB Output is correct
3 Correct 156 ms 235128 KB Output is correct
4 Correct 156 ms 235128 KB Output is correct
5 Correct 141 ms 235128 KB Output is correct
6 Correct 771 ms 236160 KB Output is correct
7 Correct 744 ms 236152 KB Output is correct
8 Correct 787 ms 236152 KB Output is correct
9 Correct 1032 ms 236108 KB Output is correct
10 Correct 1012 ms 236220 KB Output is correct
11 Correct 593 ms 235384 KB Output is correct
12 Correct 621 ms 235384 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 152 ms 235140 KB Output is correct
2 Correct 164 ms 235128 KB Output is correct
3 Correct 156 ms 235128 KB Output is correct
4 Correct 156 ms 235128 KB Output is correct
5 Correct 141 ms 235128 KB Output is correct
6 Correct 139 ms 235128 KB Output is correct
7 Correct 141 ms 235128 KB Output is correct
8 Correct 176 ms 235384 KB Output is correct
9 Correct 175 ms 235256 KB Output is correct
10 Correct 176 ms 235256 KB Output is correct
11 Correct 771 ms 236160 KB Output is correct
12 Correct 744 ms 236152 KB Output is correct
13 Correct 787 ms 236152 KB Output is correct
14 Correct 1032 ms 236108 KB Output is correct
15 Correct 1012 ms 236220 KB Output is correct
16 Correct 593 ms 235384 KB Output is correct
17 Correct 621 ms 235384 KB Output is correct
18 Correct 1225 ms 236184 KB Output is correct
19 Correct 1279 ms 236280 KB Output is correct
20 Runtime error 1933 ms 478044 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -