oj.uz

답안 #277999

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
277999 2020-08-21T08:28:34 Z arnold518 Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 2000 ms 233364 KB 
#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")

#include "happiness.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll INF = 1e18;
const int MAXVAL = 8e6;

ll M;
map<ll, int> MM;

struct Node
{
	ll val, lazy;
	int lc, rc;
	Node() : val(0), lazy(0), lc(-1), rc(-1) {} 
};

Node nodes[MAXVAL];
vector<int> pool;

int newNode()
{
	int t=pool.back(); pool.pop_back();
	return t;
}

void deleteNode(int node)
{
	pool.push_back(node);
	nodes[node]=Node();
}	

void busy(int node, ll tl, ll tr)
{
	if(nodes[node].lazy==0) return;
	nodes[node].val+=nodes[node].lazy;
	if(tl!=tr)
	{
		if(nodes[node].lc==-1) nodes[node].lc=newNode();
		nodes[nodes[node].lc].lazy+=nodes[node].lazy;
		if(nodes[node].rc==-1) nodes[node].rc=newNode();
		nodes[nodes[node].rc].lazy+=nodes[node].lazy;
	}
	nodes[node].lazy=0;
}

void update(int node, ll tl, ll tr, ll l, ll r, ll k)
{
	if(r<tl || tr<l) return;
	if(l<=tl && tr<=r)
	{
		nodes[node].lazy+=k;
		return;
	}

	busy(node, tl, tr);
	ll mid=tl+tr>>1;

	if(l<=mid)
	{
		if(nodes[node].lc==-1) nodes[node].lc=newNode();
		update(nodes[node].lc, tl, mid, l, r, k);
	}
	if(mid+1<=r)
	{
		if(nodes[node].rc==-1) nodes[node].rc=newNode();
		update(nodes[node].rc, mid+1, tr, l, r, k);
	}

	nodes[node].val=INF;
	if(nodes[node].lc!=-1)
	{
		nodes[node].val=min(nodes[node].val, nodes[nodes[node].lc].val+nodes[nodes[node].lc].lazy);
		int p=nodes[node].lc;
		if(nodes[p].lc==-1 && nodes[p].rc==-1 && nodes[p].val+nodes[p].lazy==0)
		{
			nodes[node].lc=-1;
			deleteNode(p);
		}
	}
	if(nodes[node].rc!=-1)
	{
		nodes[node].val=min(nodes[node].val, nodes[nodes[node].rc].val+nodes[nodes[node].rc].lazy);
		int p=nodes[node].rc;
		if(nodes[p].lc==-1 && nodes[p].rc==-1 && nodes[p].val+nodes[p].lazy==0)
		{
			nodes[node].rc=-1;
			deleteNode(p);
		}
	}
}

int root;

ll query()
{
	return nodes[root].val+nodes[root].lazy;
}

void push(ll x)
{
	update(root, 1, M, x+1, M, x);
	MM[x]++;
	if(MM[x]==1)
	{
		auto it=MM.find(x);
		ll val=-x;
		if(next(it)!=MM.end()) val+=next(it)->first;
		update(root, 1, M, prev(it)->first+1, x, val);
	}
}

void pop(ll x)
{
	update(root, 1, M, x+1, M, -x);
	MM[x]--;
	if(MM[x]==0)
	{
		auto it=MM.find(x);
		ll val=x;
		if(next(it)!=MM.end()) val-=next(it)->first;
		update(root, 1, M, prev(it)->first+1, x, val);
		MM.erase(x);
	}
}

bool init(int coinsCount, ll maxCoinSize, ll coins[])
{	
	for(int i=0; i<MAXVAL; i++) pool.push_back(i);
	M=maxCoinSize;
	root=newNode();
	MM[0];

	for(int i=0; i<coinsCount; i++) push(coins[i]);
	return query()>=-1;
}

bool is_happy(int event, int coinsCount, ll coins[])
{
	if(event == -1) for(int i=0; i<coinsCount; i++) pop(coins[i]);
	else for(int i=0; i<coinsCount; i++) push(coins[i]);
	return query()>=-1;
}

Compilation message

happiness.cpp: In function 'void update(int, ll, ll, ll, ll, ll)':
happiness.cpp:65:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |  ll mid=tl+tr>>1;
      |         ~~^~~
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 159 ms 221140 KB Output is correct
2 Correct 162 ms 221132 KB Output is correct
3 Correct 161 ms 221132 KB Output is correct
4 Correct 163 ms 221128 KB Output is correct
5 Correct 189 ms 221116 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 159 ms 221140 KB Output is correct
2 Correct 162 ms 221132 KB Output is correct
3 Correct 161 ms 221132 KB Output is correct
4 Correct 163 ms 221128 KB Output is correct
5 Correct 189 ms 221116 KB Output is correct
6 Correct 183 ms 221132 KB Output is correct
7 Correct 170 ms 221260 KB Output is correct
8 Correct 217 ms 221388 KB Output is correct
9 Correct 230 ms 221260 KB Output is correct
10 Correct 252 ms 221392 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 159 ms 221140 KB Output is correct
2 Correct 162 ms 221132 KB Output is correct
3 Correct 161 ms 221132 KB Output is correct
4 Correct 163 ms 221128 KB Output is correct
5 Correct 189 ms 221116 KB Output is correct
6 Correct 1244 ms 226912 KB Output is correct
7 Correct 1224 ms 227024 KB Output is correct
8 Correct 1216 ms 227080 KB Output is correct
9 Correct 1915 ms 227688 KB Output is correct
10 Correct 1969 ms 230412 KB Output is correct
11 Correct 913 ms 233120 KB Output is correct
12 Correct 945 ms 233364 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 159 ms 221140 KB Output is correct
2 Correct 162 ms 221132 KB Output is correct
3 Correct 161 ms 221132 KB Output is correct
4 Correct 163 ms 221128 KB Output is correct
5 Correct 189 ms 221116 KB Output is correct
6 Correct 183 ms 221132 KB Output is correct
7 Correct 170 ms 221260 KB Output is correct
8 Correct 217 ms 221388 KB Output is correct
9 Correct 230 ms 221260 KB Output is correct
10 Correct 252 ms 221392 KB Output is correct
11 Correct 1244 ms 226912 KB Output is correct
12 Correct 1224 ms 227024 KB Output is correct
13 Correct 1216 ms 227080 KB Output is correct
14 Correct 1915 ms 227688 KB Output is correct
15 Correct 1969 ms 230412 KB Output is correct
16 Correct 913 ms 233120 KB Output is correct
17 Correct 945 ms 233364 KB Output is correct
18 Execution timed out 2086 ms 227944 KB Time limit exceeded
19 Halted 0 ms 0 KB -