oj.uz

Submission #526930

# Submission time Handle Problem Language Result Execution time Memory
526930 2022-02-16T16:45:11 Z peuch Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 2000 ms 425864 KB 
#include "happiness.h"
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;

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

unordered_map<long long, int> freq;

bool init(int coinsCount, long long maxCoinSize, long long coins[]);
bool is_happy(int event, int coinsCount, long long coins[]);
int create();
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);

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++){
		freq[coins[i]] += event;
		if(event == 1 && freq[coins[i]] == 1) update(1, 1, m, coins[i], coins[i], 1 - coins[i]);
		if(event == -1 && freq[coins[i]] == 0) update(1, 1, m, coins[i], coins[i], coins[i] - 1);
		sum += event * coins[i];
		update(1, 1, m, coins[i] + 1, m, event * coins[i]);
	}
	return seg[1] >= 0;
}

int create(){
	seg.push_back(0);
	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();
			e[pos] = aux;
		}
		if(d[pos] == 0){
			int aux = create();
			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();
			e[pos] = aux;
		}
		update(e[pos], ini, mid, p, q, val);
	}
	if(q > mid){
		if(d[pos] == 0){
			int aux = create();
			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]]);
}

Compilation message

happiness.cpp: In function 'void refresh(int, long long int, long long int)':
happiness.cpp:49:13: warning: unused variable 'mid' [-Wunused-variable]
   49 |   long long mid = (ini + fim) >> 1;
      |             ^~~
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 204 KB Output is correct
2 Correct 0 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 0 ms 204 KB Output is correct
2 Correct 0 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 7 ms 3512 KB Output is correct
7 Correct 9 ms 4792 KB Output is correct
8 Correct 93 ms 37256 KB Output is correct
9 Correct 87 ms 37400 KB Output is correct
10 Correct 74 ms 28244 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 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 956 ms 50084 KB Output is correct
7 Correct 895 ms 49828 KB Output is correct
8 Correct 908 ms 50044 KB Output is correct
9 Correct 1435 ms 55524 KB Output is correct
10 Correct 1359 ms 57252 KB Output is correct
11 Correct 534 ms 31944 KB Output is correct
12 Correct 492 ms 31888 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 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 7 ms 3512 KB Output is correct
7 Correct 9 ms 4792 KB Output is correct
8 Correct 93 ms 37256 KB Output is correct
9 Correct 87 ms 37400 KB Output is correct
10 Correct 74 ms 28244 KB Output is correct
11 Correct 956 ms 50084 KB Output is correct
12 Correct 895 ms 49828 KB Output is correct
13 Correct 908 ms 50044 KB Output is correct
14 Correct 1435 ms 55524 KB Output is correct
15 Correct 1359 ms 57252 KB Output is correct
16 Correct 534 ms 31944 KB Output is correct
17 Correct 492 ms 31888 KB Output is correct
18 Execution timed out 2109 ms 425864 KB Time limit exceeded
19 Halted 0 ms 0 KB -