oj.uz

Submission #946470

# Submission time Handle Problem Language Result Execution time Memory
946470 2024-03-14T16:54:03 Z infrapolar Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 2000 ms 524288 KB 
#include "happiness.h"
#include <cstdint>
#include <algorithm>
#include <functional>
#include <unordered_map>
#include <ext/pb_ds/assoc_container.hpp>
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 node_l, node_r;
	int64_t mn_diff = 0; //S - i
	Node(){}
	Node(int64_t node_l, int64_t node_r) : node_l(node_l), node_r(node_r){}
	void add_lazy(int64_t _lazy){
		mn_diff += _lazy;
	}
	void check_children(){
		if (left == -1){
			int64_t mid = (node_l + node_r)/2;
			left = storage_end++;
			right = storage_end++;
			node_storage[left] = Node(node_l, mid);
			node_storage[right] = Node(mid+1, node_r);
		}
	}
	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){
		if (l > node_r || r < node_l)
			return;
		if (l <= node_l && node_r <= r)
			return add_lazy(x);
		push();
		node_storage[left].add(l, r, x);
		node_storage[right].add(l, r, x);
		mn_diff = min(node_storage[left].mn_diff, node_storage[right].mn_diff);
	}


};
__gnu_pbds::gp_hash_table<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 );
		root.add(place+1, tree_size, sign * coins[i]);
	}
	

	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(0, tree_size);
	root.add(0, tree_size, 1);
	root.add(0, tree_size, inf);
	
	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 348 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 348 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 5724 KB Output is correct
7 Correct 5 ms 5744 KB Output is correct
8 Correct 37 ms 33464 KB Output is correct
9 Correct 36 ms 33284 KB Output is correct
10 Correct 34 ms 31388 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 771 ms 273480 KB Output is correct
7 Correct 703 ms 271532 KB Output is correct
8 Correct 751 ms 275272 KB Output is correct
9 Correct 1166 ms 404392 KB Output is correct
10 Correct 1218 ms 455624 KB Output is correct
11 Correct 685 ms 486936 KB Output is correct
12 Correct 681 ms 486444 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 5724 KB Output is correct
7 Correct 5 ms 5744 KB Output is correct
8 Correct 37 ms 33464 KB Output is correct
9 Correct 36 ms 33284 KB Output is correct
10 Correct 34 ms 31388 KB Output is correct
11 Correct 771 ms 273480 KB Output is correct
12 Correct 703 ms 271532 KB Output is correct
13 Correct 751 ms 275272 KB Output is correct
14 Correct 1166 ms 404392 KB Output is correct
15 Correct 1218 ms 455624 KB Output is correct
16 Correct 685 ms 486936 KB Output is correct
17 Correct 681 ms 486444 KB Output is correct
18 Execution timed out 3192 ms 524288 KB Time limit exceeded
19 Halted 0 ms 0 KB -