oj.uz

답안 #526888

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
526888 2022-02-16T14:21:02 Z peuch Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 1954 ms 524288 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(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){
	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(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 0;
	refresh(pos, ini, fim);
	if(ini > q || fim < p) return 0;
	if(ini >= p && fim <= q) return seg[pos];
	long long mid = (ini + fim) >> 1;
	return min(query(e[pos], ini, mid, p, q), query(d[pos], mid + 1, fim, p, q));
}

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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 7 ms 4132 KB Output is correct
7 Correct 8 ms 4496 KB Output is correct
8 Correct 75 ms 33464 KB Output is correct
9 Correct 91 ms 41784 KB Output is correct
10 Correct 67 ms 32584 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 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 622 ms 42772 KB Output is correct
7 Correct 625 ms 42728 KB Output is correct
8 Correct 620 ms 42768 KB Output is correct
9 Correct 968 ms 50020 KB Output is correct
10 Correct 939 ms 52424 KB Output is correct
11 Correct 315 ms 23064 KB Output is correct
12 Correct 298 ms 22868 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 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 7 ms 4132 KB Output is correct
7 Correct 8 ms 4496 KB Output is correct
8 Correct 75 ms 33464 KB Output is correct
9 Correct 91 ms 41784 KB Output is correct
10 Correct 67 ms 32584 KB Output is correct
11 Correct 622 ms 42772 KB Output is correct
12 Correct 625 ms 42728 KB Output is correct
13 Correct 620 ms 42768 KB Output is correct
14 Correct 968 ms 50020 KB Output is correct
15 Correct 939 ms 52424 KB Output is correct
16 Correct 315 ms 23064 KB Output is correct
17 Correct 298 ms 22868 KB Output is correct
18 Correct 1954 ms 524288 KB Output is correct
19 Runtime error 1823 ms 524288 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -