oj.uz

Submission #526890

# Submission time Handle Problem Language Result Execution time Memory
526890 2022-02-16T14:31:53 Z peuch Happiness (Balkan15_HAPPINESS) C++17
30 / 100
 1010 ms 52396 KB 
#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(0);
	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(p <= mid){
		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 1e18;
	if(ini > q || fim < p) return 1e18;
	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 0 ms 216 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 292 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 216 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 292 KB Output is correct
6 Correct 8 ms 4132 KB Output is correct
7 Correct 8 ms 4516 KB Output is correct
8 Correct 72 ms 33456 KB Output is correct
9 Correct 96 ms 41868 KB Output is correct
10 Correct 70 ms 32560 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 216 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 292 KB Output is correct
6 Correct 610 ms 42908 KB Output is correct
7 Correct 607 ms 42832 KB Output is correct
8 Correct 676 ms 42840 KB Output is correct
9 Correct 914 ms 50156 KB Output is correct
10 Correct 1010 ms 52396 KB Output is correct
11 Incorrect 325 ms 22952 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 216 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 292 KB Output is correct
6 Correct 8 ms 4132 KB Output is correct
7 Correct 8 ms 4516 KB Output is correct
8 Correct 72 ms 33456 KB Output is correct
9 Correct 96 ms 41868 KB Output is correct
10 Correct 70 ms 32560 KB Output is correct
11 Correct 610 ms 42908 KB Output is correct
12 Correct 607 ms 42832 KB Output is correct
13 Correct 676 ms 42840 KB Output is correct
14 Correct 914 ms 50156 KB Output is correct
15 Correct 1010 ms 52396 KB Output is correct
16 Incorrect 325 ms 22952 KB Output isn't correct
17 Halted 0 ms 0 KB -