oj.uz

Submission #526916

# Submission time Handle Problem Language Result Execution time Memory
526916 2022-02-16T16:24:32 Z peuch Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 1058 ms 377300 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;
	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 300 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 288 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 288 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 3 ms 3020 KB Output is correct
7 Correct 4 ms 3340 KB Output is correct
8 Correct 39 ms 25136 KB Output is correct
9 Correct 39 ms 25372 KB Output is correct
10 Correct 36 ms 24416 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 288 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 437 ms 33548 KB Output is correct
7 Correct 433 ms 33256 KB Output is correct
8 Correct 435 ms 33580 KB Output is correct
9 Correct 708 ms 40276 KB Output is correct
10 Correct 680 ms 41900 KB Output is correct
11 Correct 237 ms 18804 KB Output is correct
12 Correct 244 ms 18940 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 288 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 3 ms 3020 KB Output is correct
7 Correct 4 ms 3340 KB Output is correct
8 Correct 39 ms 25136 KB Output is correct
9 Correct 39 ms 25372 KB Output is correct
10 Correct 36 ms 24416 KB Output is correct
11 Correct 437 ms 33548 KB Output is correct
12 Correct 433 ms 33256 KB Output is correct
13 Correct 435 ms 33580 KB Output is correct
14 Correct 708 ms 40276 KB Output is correct
15 Correct 680 ms 41900 KB Output is correct
16 Correct 237 ms 18804 KB Output is correct
17 Correct 244 ms 18940 KB Output is correct
18 Incorrect 1058 ms 377300 KB Output isn't correct
19 Halted 0 ms 0 KB -