답안 #925158

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
925158 2024-02-10T21:37:33 Z myst6 Happiness (Balkan15_HAPPINESS) C++14
60 / 100
1637 ms 524288 KB
#include "happiness.h"
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
struct Node {
	ll tag, mx;
	Node *left, *right;
	Node() : tag(0), mx(0), left(nullptr), right(nullptr) {}
	void extend(ll xl, ll xr) {
		if (xl != xr && !left) {
			left = new Node();
			right = new Node();
		}
	}
	void apply(ll xl, ll xr) {
		extend(xl, xr);
		if (tag != 0) {
			mx += tag;
			if (left) left->tag += tag;
			if (right) right->tag += tag;
			tag = 0;
		}
	}
	void update(ll l, ll r, ll xl, ll xr, ll delta) {
		if (l > r) return;
		if (l == xl && r == xr) {
			tag += delta;
		} else {
			apply(xl, xr);
			ll xm = (xl + xr) / 2;
			left->update(l, min(r, xm), xl, xm, delta);
			right->update(max(l, xm+1), r, xm+1, xr, delta);
			left->apply(xl, xm); right->apply(xm+1, xr);
			mx = max(left->mx, right->mx);
		}
	}
} tree;
 
const ll hi = 1'000'000'000'005LL;
 
map<ll,int> cnt;
 
void add(ll coin) {
	cnt[coin] += 1;
	if (cnt[coin] == 1) tree.update(coin, coin, 1, hi, +coin);
	tree.update(coin+1, hi, 1, hi, -coin);
}
 
void remove(ll coin) {
	cnt[coin] -= 1;
	if (cnt[coin] == 0) {
		tree.update(coin, coin, 1, hi, -coin);
		cnt.erase(coin);
	}
	tree.update(coin+1, hi, 1, hi, +coin);
}
 
bool check() {
	tree.apply(1, hi);
	return tree.mx <= 1;
}
 
bool init(int coinsCount, ll maxCoinSize, ll coins[]) {
	for (int i=0; i<coinsCount; i++) add(coins[i]);
	return check();
}
 
bool is_happy(int event, int coinsCount, ll coins[]) {
	for (int i=0; i<coinsCount; i++) 
		if (event == 1) add(coins[i]);
		else remove(coins[i]);
	return check();
}

Compilation message

grader.cpp: In function 'int main()':
grader.cpp:16:12: warning: unused variable 'max_code' [-Wunused-variable]
   16 |  long long max_code;
      |            ^~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 6 ms 5980 KB Output is correct
7 Correct 7 ms 6488 KB Output is correct
8 Correct 65 ms 51100 KB Output is correct
9 Correct 68 ms 51420 KB Output is correct
10 Correct 59 ms 49840 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 884 ms 70632 KB Output is correct
7 Correct 865 ms 69768 KB Output is correct
8 Correct 882 ms 70132 KB Output is correct
9 Correct 1509 ms 83804 KB Output is correct
10 Correct 1637 ms 92372 KB Output is correct
11 Correct 639 ms 47388 KB Output is correct
12 Correct 599 ms 47784 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 6 ms 5980 KB Output is correct
7 Correct 7 ms 6488 KB Output is correct
8 Correct 65 ms 51100 KB Output is correct
9 Correct 68 ms 51420 KB Output is correct
10 Correct 59 ms 49840 KB Output is correct
11 Correct 884 ms 70632 KB Output is correct
12 Correct 865 ms 69768 KB Output is correct
13 Correct 882 ms 70132 KB Output is correct
14 Correct 1509 ms 83804 KB Output is correct
15 Correct 1637 ms 92372 KB Output is correct
16 Correct 639 ms 47388 KB Output is correct
17 Correct 599 ms 47784 KB Output is correct
18 Runtime error 1178 ms 524288 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -