oj.uz

답안 #278274

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
278274 2020-08-21T11:35:04 Z arnold518 Happiness (Balkan15_HAPPINESS) C++14
30 / 100
 2000 ms 212824 KB 
#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, sum;
	int lc, rc;
	Node() : val(0), sum(0), lc(-1), rc(-1) {} 
};

Node nodes[MAXVAL];
int ncnt=0;

int newNode()
{
	return ncnt++;
}

void update(int node, ll tl, ll tr, vector<pll> &V)
{
	if(tl==tr)
	{
		for(auto it : V) nodes[node].sum+=it.second, nodes[node].val+=it.second;
		return;
	}
	ll mid=tl+tr>>1;
	vector<pll> L, R;
	for(auto it : V)
	{
		if(it.first<=mid) L.push_back(it);
		else R.push_back(it);
	}
	if(!L.empty())
	{
		if(nodes[node].lc==-1) nodes[node].lc=newNode();
		update(nodes[node].lc, tl, mid, L);
	}
	if(!R.empty())
	{
		if(nodes[node].rc==-1) nodes[node].rc=newNode();
		update(nodes[node].rc, mid+1, tr, R);
	}

	nodes[node].sum=0; nodes[node].val=0;
	if(nodes[node].lc!=-1) nodes[node].sum+=nodes[nodes[node].lc].sum;

	if(nodes[node].lc!=-1) nodes[node].val=min(nodes[node].val, nodes[nodes[node].lc].val);
	if(nodes[node].rc!=-1) nodes[node].val=min(nodes[node].val, nodes[node].sum+nodes[nodes[node].rc].val);
	nodes[node].val=min(nodes[node].val, nodes[node].sum);

	if(nodes[node].rc!=-1) nodes[node].sum+=nodes[nodes[node].rc].sum;

}

int root;

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

vector<pll> V;

void update2(ll l, ll r, ll x)
{
	if(r<l) return;
	if(l<=M) V.push_back({l, x});
	if(r+1<=M) V.push_back({r+1, -x});
}

void push(ll x)
{
	update2(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;
		update2(prev(it)->first+1, x, val);
	}
}

void pop(ll x)
{
	update2(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;
		update2(prev(it)->first+1, x, val);
		MM.erase(x);
	}
}

bool init(int coinsCount, ll maxCoinSize, ll coins[])
{
	V.clear();
	M=maxCoinSize;
	root=newNode();
	MM[0];

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

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

Compilation message

happiness.cpp: In function 'void update(int, ll, ll, std::vector<std::pair<long long int, long long int> >&)':
happiness.cpp:37:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |  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 119 ms 188152 KB Output is correct
2 Correct 165 ms 188152 KB Output is correct
3 Correct 113 ms 188160 KB Output is correct
4 Correct 174 ms 188192 KB Output is correct
5 Correct 113 ms 188156 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 119 ms 188152 KB Output is correct
2 Correct 165 ms 188152 KB Output is correct
3 Correct 113 ms 188160 KB Output is correct
4 Correct 174 ms 188192 KB Output is correct
5 Correct 113 ms 188156 KB Output is correct
6 Correct 136 ms 188480 KB Output is correct
7 Correct 129 ms 188408 KB Output is correct
8 Correct 290 ms 190704 KB Output is correct
9 Correct 207 ms 190576 KB Output is correct
10 Correct 224 ms 190576 KB Output is correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 119 ms 188152 KB Output is correct
2 Correct 165 ms 188152 KB Output is correct
3 Correct 113 ms 188160 KB Output is correct
4 Correct 174 ms 188192 KB Output is correct
5 Correct 113 ms 188156 KB Output is correct
6 Execution timed out 2077 ms 212824 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 119 ms 188152 KB Output is correct
2 Correct 165 ms 188152 KB Output is correct
3 Correct 113 ms 188160 KB Output is correct
4 Correct 174 ms 188192 KB Output is correct
5 Correct 113 ms 188156 KB Output is correct
6 Correct 136 ms 188480 KB Output is correct
7 Correct 129 ms 188408 KB Output is correct
8 Correct 290 ms 190704 KB Output is correct
9 Correct 207 ms 190576 KB Output is correct
10 Correct 224 ms 190576 KB Output is correct
11 Execution timed out 2077 ms 212824 KB Time limit exceeded
12 Halted 0 ms 0 KB -