oj.uz

Submission #946539

# Submission time Handle Problem Language Result Execution time Memory
946539 2024-03-14T18:15:57 Z infrapolar Happiness (Balkan15_HAPPINESS) C++17
100 / 100
 1644 ms 470064 KB 
#include "happiness.h"
#include <cstdint>
#include <algorithm>
#include <functional>
#include <map>
using namespace std;
struct Node;
int64_t tree_block = 7e5; // 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 M;
int64_t find_to_insert(int64_t coin){
	return (tree_block * coin) + (cur_ptr[coin]++);
}
int64_t find_to_delete(int64_t coin){
	return (tree_block * coin) + (--cur_ptr[coin]);
}

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, -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);
	
	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 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct
6 Correct 3 ms 5600 KB Output is correct
7 Correct 4 ms 5468 KB Output is correct
8 Correct 36 ms 18476 KB Output is correct
9 Correct 31 ms 18592 KB Output is correct
10 Correct 29 ms 18404 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct
6 Correct 672 ms 141524 KB Output is correct
7 Correct 673 ms 138980 KB Output is correct
8 Correct 688 ms 141164 KB Output is correct
9 Correct 1160 ms 199804 KB Output is correct
10 Correct 1129 ms 227664 KB Output is correct
11 Correct 577 ms 243012 KB Output is correct
12 Correct 580 ms 242872 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct
6 Correct 3 ms 5600 KB Output is correct
7 Correct 4 ms 5468 KB Output is correct
8 Correct 36 ms 18476 KB Output is correct
9 Correct 31 ms 18592 KB Output is correct
10 Correct 29 ms 18404 KB Output is correct
11 Correct 672 ms 141524 KB Output is correct
12 Correct 673 ms 138980 KB Output is correct
13 Correct 688 ms 141164 KB Output is correct
14 Correct 1160 ms 199804 KB Output is correct
15 Correct 1129 ms 227664 KB Output is correct
16 Correct 577 ms 243012 KB Output is correct
17 Correct 580 ms 242872 KB Output is correct
18 Correct 1039 ms 278500 KB Output is correct
19 Correct 1014 ms 288784 KB Output is correct
20 Correct 1644 ms 470064 KB Output is correct
21 Correct 981 ms 248740 KB Output is correct
22 Correct 780 ms 244000 KB Output is correct
23 Correct 769 ms 244484 KB Output is correct
24 Correct 959 ms 271912 KB Output is correct