oj.uz

Submission #526946

# Submission time Handle Problem Language Result Execution time Memory
526946 2022-02-16T17:06:24 Z peuch Happiness (Balkan15_HAPPINESS) C++17
100 / 100
 1773 ms 423136 KB 
#include "happiness.h"
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;

long long m;
vector<long long> seg, lzy;
vector<int> e, d, cnt;

bool init(int coinsCount, long long maxCoinSize, long long coins[]);
bool is_happy(int event, int coinsCount, long long coins[]);
int create();
void update(int pos, long long ini, long long fim, long long p, long long q, long long val, bool tp);

bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
	m = maxCoinSize;
	create();
	create();
	return is_happy(1, coinsCount, coins);
}

bool is_happy(int event, int coinsCount, long long coins[]) {
	for(int i = 0; i < coinsCount; i++){
		update(1, 1, m, coins[i], coins[i], (-event) * (coins[i] - 1), 1);
		update(1, 1, m, coins[i] + 1, m, event * coins[i], 0);
	}
	return seg[1] + lzy[1] >= 0;
}

int create(){
	seg.push_back(0);
	lzy.push_back(0);
	e.push_back(0);
	d.push_back(0);
	cnt.push_back(0);
	return seg.size() - 1;
}

void update(int pos, long long ini, long long fim, long long p, long long q, long long val, bool tp){
	if(ini > q || fim < p) return;
	if(ini >= p && fim <= q){
		if(tp){
			if(val >= 0) cnt[pos]--;
			if(cnt[pos] == 0) seg[pos] += val;
			if(val < 0) cnt[pos]++;
		}
		else{
			seg[pos] += val;
			lzy[pos] += val;
		}
		return;
	}
	long long mid = (ini + fim) >> 1;
	if(e[pos] == 0){
		int aux = create();
		e[pos] = aux;
	}
	if(d[pos] == 0){
		int aux = create();
		d[pos] = aux;
	}
	update(e[pos], ini, mid, p, q, val, tp);
	update(d[pos], mid + 1, fim, p, q, val, tp);
	seg[pos] = min(seg[e[pos]], seg[d[pos]]) + 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 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 4 ms 2240 KB Output is correct
7 Correct 4 ms 2880 KB Output is correct
8 Correct 44 ms 21608 KB Output is correct
9 Correct 44 ms 21764 KB Output is correct
10 Correct 50 ms 21332 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 504 ms 42372 KB Output is correct
7 Correct 466 ms 33776 KB Output is correct
8 Correct 449 ms 42380 KB Output is correct
9 Correct 752 ms 48096 KB Output is correct
10 Correct 767 ms 50260 KB Output is correct
11 Correct 291 ms 25172 KB Output is correct
12 Correct 312 ms 25236 KB Output is correct

Subtask #4
40.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 4 ms 2240 KB Output is correct
7 Correct 4 ms 2880 KB Output is correct
8 Correct 44 ms 21608 KB Output is correct
9 Correct 44 ms 21764 KB Output is correct
10 Correct 50 ms 21332 KB Output is correct
11 Correct 504 ms 42372 KB Output is correct
12 Correct 466 ms 33776 KB Output is correct
13 Correct 449 ms 42380 KB Output is correct
14 Correct 752 ms 48096 KB Output is correct
15 Correct 767 ms 50260 KB Output is correct
16 Correct 291 ms 25172 KB Output is correct
17 Correct 312 ms 25236 KB Output is correct
18 Correct 1185 ms 296816 KB Output is correct
19 Correct 1194 ms 301988 KB Output is correct
20 Correct 1773 ms 423136 KB Output is correct
21 Correct 1006 ms 221352 KB Output is correct
22 Correct 540 ms 30848 KB Output is correct
23 Correct 556 ms 31504 KB Output is correct
24 Correct 1127 ms 302228 KB Output is correct