oj.uz

Submission #526895

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

long long m, sum;
vector<long long> seg, lzy;
vector<int> 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 0 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 0 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 5 ms 3516 KB Output is correct
7 Correct 6 ms 3768 KB Output is correct
8 Correct 58 ms 30460 KB Output is correct
9 Correct 72 ms 38720 KB Output is correct
10 Correct 54 ms 29808 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 518 ms 40432 KB Output is correct
7 Correct 526 ms 40296 KB Output is correct
8 Correct 570 ms 40468 KB Output is correct
9 Correct 801 ms 45056 KB Output is correct
10 Correct 867 ms 46676 KB Output is correct
11 Correct 295 ms 22356 KB Output is correct
12 Correct 277 ms 22896 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 5 ms 3516 KB Output is correct
7 Correct 6 ms 3768 KB Output is correct
8 Correct 58 ms 30460 KB Output is correct
9 Correct 72 ms 38720 KB Output is correct
10 Correct 54 ms 29808 KB Output is correct
11 Correct 518 ms 40432 KB Output is correct
12 Correct 526 ms 40296 KB Output is correct
13 Correct 570 ms 40468 KB Output is correct
14 Correct 801 ms 45056 KB Output is correct
15 Correct 867 ms 46676 KB Output is correct
16 Correct 295 ms 22356 KB Output is correct
17 Correct 277 ms 22896 KB Output is correct
18 Correct 1528 ms 394608 KB Output is correct
19 Runtime error 1551 ms 524292 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -