oj.uz

Submission #946561

# Submission time Handle Problem Language Result Execution time Memory
946561 2024-03-14T18:35:10 Z infrapolar Happiness (Balkan15_HAPPINESS) C++17
100 / 100
 1556 ms 446100 KB 
#include "happiness.h"
#include <cstdint>
#include <algorithm>
#include <functional>
#include <map>
using namespace std;
struct Node;
int64_t tree_block = 2e5; // N
int64_t tree_size ; // M*N
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 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 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 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 4 ms 5468 KB Output is correct
7 Correct 4 ms 5544 KB Output is correct
8 Correct 38 ms 18212 KB Output is correct
9 Correct 32 ms 18380 KB Output is correct
10 Correct 28 ms 18004 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 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 705 ms 128968 KB Output is correct
7 Correct 657 ms 126868 KB Output is correct
8 Correct 666 ms 129008 KB Output is correct
9 Correct 1079 ms 182980 KB Output is correct
10 Correct 1101 ms 206728 KB Output is correct
11 Correct 564 ms 222396 KB Output is correct
12 Correct 540 ms 222328 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 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 4 ms 5468 KB Output is correct
7 Correct 4 ms 5544 KB Output is correct
8 Correct 38 ms 18212 KB Output is correct
9 Correct 32 ms 18380 KB Output is correct
10 Correct 28 ms 18004 KB Output is correct
11 Correct 705 ms 128968 KB Output is correct
12 Correct 657 ms 126868 KB Output is correct
13 Correct 666 ms 129008 KB Output is correct
14 Correct 1079 ms 182980 KB Output is correct
15 Correct 1101 ms 206728 KB Output is correct
16 Correct 564 ms 222396 KB Output is correct
17 Correct 540 ms 222328 KB Output is correct
18 Correct 1002 ms 264952 KB Output is correct
19 Correct 1027 ms 273484 KB Output is correct
20 Correct 1556 ms 446100 KB Output is correct
21 Correct 917 ms 235732 KB Output is correct
22 Correct 744 ms 222552 KB Output is correct
23 Correct 739 ms 222628 KB Output is correct
24 Correct 944 ms 256900 KB Output is correct