oj.uz

Submission #526923

# Submission time Handle Problem Language Result Execution time Memory
526923 2022-02-16T16:38:55 Z peuch Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 1768 ms 390148 KB 
#include "happiness.h"
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 16000000;

long long m, sum;
long long seg[MAXN], lzy[MAXN];
int e[MAXN], d[MAXN];
int ind = -1;

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(){
	ind++;
	seg[ind] = 0;
	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();
			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:52:13: warning: unused variable 'mid' [-Wunused-variable]
   52 |   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 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 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 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 5 ms 3148 KB Output is correct
7 Correct 7 ms 3532 KB Output is correct
8 Correct 57 ms 26296 KB Output is correct
9 Correct 59 ms 26480 KB Output is correct
10 Correct 54 ms 25540 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 938 ms 46636 KB Output is correct
7 Correct 959 ms 46136 KB Output is correct
8 Correct 959 ms 46644 KB Output is correct
9 Correct 1512 ms 57484 KB Output is correct
10 Correct 1558 ms 61572 KB Output is correct
11 Correct 581 ms 39428 KB Output is correct
12 Correct 564 ms 39248 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 5 ms 3148 KB Output is correct
7 Correct 7 ms 3532 KB Output is correct
8 Correct 57 ms 26296 KB Output is correct
9 Correct 59 ms 26480 KB Output is correct
10 Correct 54 ms 25540 KB Output is correct
11 Correct 938 ms 46636 KB Output is correct
12 Correct 959 ms 46136 KB Output is correct
13 Correct 959 ms 46644 KB Output is correct
14 Correct 1512 ms 57484 KB Output is correct
15 Correct 1558 ms 61572 KB Output is correct
16 Correct 581 ms 39428 KB Output is correct
17 Correct 564 ms 39248 KB Output is correct
18 Incorrect 1768 ms 390148 KB Output isn't correct
19 Halted 0 ms 0 KB -