oj.uz

Submission #946480

# Submission time Handle Problem Language Result Execution time Memory
946480 2024-03-14T17:05:57 Z infrapolar Happiness (Balkan15_HAPPINESS) C++17
100 / 100
 1584 ms 472804 KB 
#include "happiness.h"
#include <cstdint>
#include <algorithm>
#include <functional>
#include <map>
using namespace std;
struct Node;
int64_t tree_block = 7.1e5; // N+K*Q
int64_t tree_size ; // M*(N+K*Q)
int64_t mem[(int)6e7];
Node* node_storage = (Node*)mem;
int storage_end = 0;
struct Node{
	int left = -1, right = -1;
	int64_t mn_diff = 0; //S - i
	Node(){}
	void add_lazy(int64_t _lazy){
		mn_diff += _lazy;
	}
	void check_children(){
		if (left == -1){
			left = storage_end++;
			right = storage_end++;
			node_storage[left] = Node();
			node_storage[right] = Node();
		}
	}
	void push(){
		check_children();
		int64_t lazy = mn_diff - min(node_storage[left].mn_diff, node_storage[right].mn_diff);
		node_storage[left].add_lazy(lazy);
		node_storage[right].add_lazy(lazy);
	}
	void add(int64_t l, int64_t r, int64_t x, int64_t node_l, int64_t node_r){
		if (l > node_r || r < node_l)
			return;
		if (l <= node_l && node_r <= r)
			return add_lazy(x);
		push();
		int64_t mid = (node_l + node_r)/2;
		node_storage[left].add(l, r, x, node_l, mid);
		node_storage[right].add(l, r, x, mid+1, node_r);
		mn_diff = min(node_storage[left].mn_diff, node_storage[right].mn_diff);
	}


};
unordered_map<int64_t, int64_t> cur_ptr;
Node root;
int64_t inf = tree_size*2;
int64_t M;
int64_t find_to_insert(int64_t x){
	return (tree_block * x) + (cur_ptr[x]++);
}
int64_t find_to_delete(int64_t x){
	return (tree_block * x) + (--cur_ptr[x]);
}

bool is_happy(int event, int coinsCount, long long coins[]) {
	int sign = event;
	function<int64_t(int64_t)> find_place = find_to_insert;
	if (event == -1)
		find_place = find_to_delete;
	for (int i = 0; i < coinsCount; i++)
	{
		int64_t place = find_place(coins[i]);
		root.add(place, place, (-inf-coins[i]) * sign, 0, tree_size);
		root.add(place+1, tree_size, sign * coins[i], 0, tree_size);
	}
	

	return root.mn_diff >= 0;
}
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
	M = maxCoinSize;
	tree_size = (M+1)*tree_block;
	root = Node();
	root.add(0, tree_size, 1, 0, tree_size);
	root.add(0, tree_size, inf, 0, tree_size);
	
	return is_happy(1, coinsCount, coins);
}

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 0 ms 600 KB Output is correct
2 Correct 0 ms 348 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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 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 4 ms 3416 KB Output is correct
7 Correct 3 ms 3416 KB Output is correct
8 Correct 30 ms 16220 KB Output is correct
9 Correct 30 ms 16284 KB Output is correct
10 Correct 26 ms 16204 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 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 679 ms 138440 KB Output is correct
7 Correct 604 ms 135800 KB Output is correct
8 Correct 613 ms 137844 KB Output is correct
9 Correct 1049 ms 195952 KB Output is correct
10 Correct 1089 ms 223996 KB Output is correct
11 Correct 545 ms 238984 KB Output is correct
12 Correct 551 ms 238992 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 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 4 ms 3416 KB Output is correct
7 Correct 3 ms 3416 KB Output is correct
8 Correct 30 ms 16220 KB Output is correct
9 Correct 30 ms 16284 KB Output is correct
10 Correct 26 ms 16204 KB Output is correct
11 Correct 679 ms 138440 KB Output is correct
12 Correct 604 ms 135800 KB Output is correct
13 Correct 613 ms 137844 KB Output is correct
14 Correct 1049 ms 195952 KB Output is correct
15 Correct 1089 ms 223996 KB Output is correct
16 Correct 545 ms 238984 KB Output is correct
17 Correct 551 ms 238992 KB Output is correct
18 Correct 974 ms 279904 KB Output is correct
19 Correct 988 ms 290068 KB Output is correct
20 Correct 1584 ms 472804 KB Output is correct
21 Correct 926 ms 249640 KB Output is correct
22 Correct 783 ms 244960 KB Output is correct
23 Correct 804 ms 245200 KB Output is correct
24 Correct 956 ms 273264 KB Output is correct