oj.uz

Submission #526917

# Submission time Handle Problem Language Result Execution time Memory
526917 2022-02-16T16:25:51 Z peuch Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 1477 ms 524288 KB 
#include "happiness.h"
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 16'000'000;

long long m, sum;
long long seg[MAXN], lzy[MAXN];
int e[MAXN], d[MAXN];
int ind = -1;

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){
	++ind;
	assert(ind < MAXN);
	seg[ind] = -fim;
	lzy[ind] = 0;
	e[ind] = 0;
	d[ind] = 0;
	return ind;
}

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

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 4 ms 3020 KB Output is correct
7 Correct 5 ms 3344 KB Output is correct
8 Correct 41 ms 24988 KB Output is correct
9 Correct 42 ms 25196 KB Output is correct
10 Correct 42 ms 24348 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 488 ms 32076 KB Output is correct
7 Correct 466 ms 31680 KB Output is correct
8 Correct 460 ms 32008 KB Output is correct
9 Correct 748 ms 37340 KB Output is correct
10 Correct 737 ms 39240 KB Output is correct
11 Correct 292 ms 17028 KB Output is correct
12 Correct 292 ms 17032 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 4 ms 3020 KB Output is correct
7 Correct 5 ms 3344 KB Output is correct
8 Correct 41 ms 24988 KB Output is correct
9 Correct 42 ms 25196 KB Output is correct
10 Correct 42 ms 24348 KB Output is correct
11 Correct 488 ms 32076 KB Output is correct
12 Correct 466 ms 31680 KB Output is correct
13 Correct 460 ms 32008 KB Output is correct
14 Correct 748 ms 37340 KB Output is correct
15 Correct 737 ms 39240 KB Output is correct
16 Correct 292 ms 17028 KB Output is correct
17 Correct 292 ms 17032 KB Output is correct
18 Runtime error 1477 ms 524288 KB Execution killed with signal 6
19 Halted 0 ms 0 KB -