oj.uz

Submission #946471

# Submission time Handle Problem Language Result Execution time Memory
946471 2024-03-14T16:55:12 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::cc_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 1 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 400 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 1 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 400 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 4 ms 5468 KB Output is correct
7 Correct 4 ms 5468 KB Output is correct
8 Correct 36 ms 32744 KB Output is correct
9 Correct 36 ms 32652 KB Output is correct
10 Correct 33 ms 30756 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 400 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 769 ms 264652 KB Output is correct
7 Correct 755 ms 262348 KB Output is correct
8 Correct 777 ms 266684 KB Output is correct
9 Correct 1256 ms 383984 KB Output is correct
10 Correct 1330 ms 439540 KB Output is correct
11 Correct 705 ms 468744 KB Output is correct
12 Correct 706 ms 468912 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 400 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 4 ms 5468 KB Output is correct
7 Correct 4 ms 5468 KB Output is correct
8 Correct 36 ms 32744 KB Output is correct
9 Correct 36 ms 32652 KB Output is correct
10 Correct 33 ms 30756 KB Output is correct
11 Correct 769 ms 264652 KB Output is correct
12 Correct 755 ms 262348 KB Output is correct
13 Correct 777 ms 266684 KB Output is correct
14 Correct 1256 ms 383984 KB Output is correct
15 Correct 1330 ms 439540 KB Output is correct
16 Correct 705 ms 468744 KB Output is correct
17 Correct 706 ms 468912 KB Output is correct
18 Execution timed out 3313 ms 524288 KB Time limit exceeded
19 Halted 0 ms 0 KB -