oj.uz

Submission #526907

# Submission time Handle Problem Language Result Execution time Memory
526907 2022-02-16T15:56:47 Z peuch Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 1670 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;
	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){
	// refresh(pos, ini, fim);
	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 296 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 304 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 296 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 304 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 6 ms 3540 KB Output is correct
7 Correct 7 ms 3736 KB Output is correct
8 Correct 66 ms 30692 KB Output is correct
9 Correct 74 ms 38828 KB Output is correct
10 Correct 59 ms 30040 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 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 304 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 580 ms 43556 KB Output is correct
7 Correct 579 ms 43488 KB Output is correct
8 Correct 625 ms 43636 KB Output is correct
9 Correct 881 ms 48336 KB Output is correct
10 Correct 894 ms 49908 KB Output is correct
11 Correct 313 ms 25776 KB Output is correct
12 Correct 302 ms 25704 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 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 304 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 6 ms 3540 KB Output is correct
7 Correct 7 ms 3736 KB Output is correct
8 Correct 66 ms 30692 KB Output is correct
9 Correct 74 ms 38828 KB Output is correct
10 Correct 59 ms 30040 KB Output is correct
11 Correct 580 ms 43556 KB Output is correct
12 Correct 579 ms 43488 KB Output is correct
13 Correct 625 ms 43636 KB Output is correct
14 Correct 881 ms 48336 KB Output is correct
15 Correct 894 ms 49908 KB Output is correct
16 Correct 313 ms 25776 KB Output is correct
17 Correct 302 ms 25704 KB Output is correct
18 Correct 1670 ms 396592 KB Output is correct
19 Runtime error 1635 ms 524292 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -