oj.uz

Submission #526897

# Submission time Handle Problem Language Result Execution time Memory
526897 2022-02-16T14:52:13 Z peuch Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 1607 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){
	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 5 ms 3512 KB Output is correct
7 Correct 6 ms 3768 KB Output is correct
8 Correct 60 ms 30440 KB Output is correct
9 Correct 70 ms 38688 KB Output is correct
10 Correct 55 ms 29876 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 559 ms 40640 KB Output is correct
7 Correct 655 ms 40404 KB Output is correct
8 Correct 668 ms 40548 KB Output is correct
9 Correct 857 ms 44984 KB Output is correct
10 Correct 965 ms 46504 KB Output is correct
11 Correct 342 ms 22424 KB Output is correct
12 Correct 296 ms 22448 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 5 ms 3512 KB Output is correct
7 Correct 6 ms 3768 KB Output is correct
8 Correct 60 ms 30440 KB Output is correct
9 Correct 70 ms 38688 KB Output is correct
10 Correct 55 ms 29876 KB Output is correct
11 Correct 559 ms 40640 KB Output is correct
12 Correct 655 ms 40404 KB Output is correct
13 Correct 668 ms 40548 KB Output is correct
14 Correct 857 ms 44984 KB Output is correct
15 Correct 965 ms 46504 KB Output is correct
16 Correct 342 ms 22424 KB Output is correct
17 Correct 296 ms 22448 KB Output is correct
18 Correct 1572 ms 391360 KB Output is correct
19 Runtime error 1607 ms 524292 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -