Submission #526888

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
526888	2022-02-16T14:21:02 Z	peuch	Happiness (Balkan15_HAPPINESS)	C++17	60 / 100	1954 ms	524288 KB

happiness

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

long long m, sum;
vector<long long> seg, lzy, e, d;

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

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

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

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

void refresh(int pos, long long ini, long long fim){
	if(lzy[pos] == 0) return;
	seg[pos] += lzy[pos];
	if(ini != fim){
		long long mid = (ini + fim) >> 1;
		if(e[pos] == 0){
			int aux = create(mid);
			e[pos] = aux;
		}
		if(d[pos] == 0){
			int aux = create(fim);
			d[pos] = aux;
		}
		lzy[e[pos]] += lzy[pos];
		lzy[d[pos]] += lzy[pos];
	}
	lzy[pos] = 0;
}

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

long long query(int pos, long long ini, long long fim, long long p, long long q){
	if(pos == 0) return 0;
	refresh(pos, ini, fim);
	if(ini > q || fim < p) return 0;
	if(ini >= p && fim <= q) return seg[pos];
	long long mid = (ini + fim) >> 1;
	return min(query(e[pos], ini, mid, p, q), query(d[pos], mid + 1, fim, p, q));
}

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	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	7 ms	4132 KB	Output is correct
7	Correct	8 ms	4496 KB	Output is correct
8	Correct	75 ms	33464 KB	Output is correct
9	Correct	91 ms	41784 KB	Output is correct
10	Correct	67 ms	32584 KB	Output is correct

Subtask #3

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	622 ms	42772 KB	Output is correct
7	Correct	625 ms	42728 KB	Output is correct
8	Correct	620 ms	42768 KB	Output is correct
9	Correct	968 ms	50020 KB	Output is correct
10	Correct	939 ms	52424 KB	Output is correct
11	Correct	315 ms	23064 KB	Output is correct
12	Correct	298 ms	22868 KB	Output is correct

Subtask #4

0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	7 ms	4132 KB	Output is correct
7	Correct	8 ms	4496 KB	Output is correct
8	Correct	75 ms	33464 KB	Output is correct
9	Correct	91 ms	41784 KB	Output is correct
10	Correct	67 ms	32584 KB	Output is correct
11	Correct	622 ms	42772 KB	Output is correct
12	Correct	625 ms	42728 KB	Output is correct
13	Correct	620 ms	42768 KB	Output is correct
14	Correct	968 ms	50020 KB	Output is correct
15	Correct	939 ms	52424 KB	Output is correct
16	Correct	315 ms	23064 KB	Output is correct
17	Correct	298 ms	22868 KB	Output is correct
18	Correct	1954 ms	524288 KB	Output is correct
19	Runtime error	1823 ms	524288 KB	Execution killed with signal 9
20	Halted	0 ms	0 KB	-