Submission #526946

#	Time	Username	Problem	Language	Result	Execution time	Memory
526946		peuch	Happiness (Balkan15_HAPPINESS)	C++17	100 / 100	1773 ms	423136 KiB

happiness

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

long long m;
vector<long long> seg, lzy;
vector<int> e, d, cnt;

bool init(int coinsCount, long long maxCoinSize, long long coins[]);
bool is_happy(int event, int coinsCount, long long coins[]);
int create();
void update(int pos, long long ini, long long fim, long long p, long long q, long long val, bool tp);

bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
	m = maxCoinSize;
	create();
	create();
	return is_happy(1, coinsCount, coins);
}

bool is_happy(int event, int coinsCount, long long coins[]) {
	for(int i = 0; i < coinsCount; i++){
		update(1, 1, m, coins[i], coins[i], (-event) * (coins[i] - 1), 1);
		update(1, 1, m, coins[i] + 1, m, event * coins[i], 0);
	}
	return seg[1] + lzy[1] >= 0;
}

int create(){
	seg.push_back(0);
	lzy.push_back(0);
	e.push_back(0);
	d.push_back(0);
	cnt.push_back(0);
	return seg.size() - 1;
}

void update(int pos, long long ini, long long fim, long long p, long long q, long long val, bool tp){
	if(ini > q || fim < p) return;
	if(ini >= p && fim <= q){
		if(tp){
			if(val >= 0) cnt[pos]--;
			if(cnt[pos] == 0) seg[pos] += val;
			if(val < 0) cnt[pos]++;
		}
		else{
			seg[pos] += val;
			lzy[pos] += val;
		}
		return;
	}
	long long mid = (ini + fim) >> 1;
	if(e[pos] == 0){
		int aux = create();
		e[pos] = aux;
	}
	if(d[pos] == 0){
		int aux = create();
		d[pos] = aux;
	}
	update(e[pos], ini, mid, p, q, val, tp);
	update(d[pos], mid + 1, fim, p, q, val, tp);
	seg[pos] = min(seg[e[pos]], seg[d[pos]]) + lzy[pos];
}

Compilation message (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40