oj.uz

Submission #946451

# Submission time Handle Problem Language Result Execution time Memory
946451 2024-03-14T16:39:28 Z infrapolar Happiness (Balkan15_HAPPINESS) C++17
30 / 100
 1338 ms 524288 KB 
#include "happiness.h"
#include <cstdint>
#include <algorithm>
#include <functional>
#include <unordered_map>
using namespace std;
int64_t tree_block = 7.1e5; // N+K*Q
int64_t tree_size ; // M*(N+K*Q)
struct Node{
	Node *left = nullptr, *right = nullptr;
	int64_t node_l, node_r;
	int64_t mn_diff = 0; //S - i
	int64_t lazy = 0;
	Node(){}
	Node(int64_t node_l, int64_t node_r) : node_l(node_l), node_r(node_r){}
	void add_lazy(int64_t _lazy){
		lazy += _lazy;
		mn_diff += _lazy;
	}
	void check_children(){
		if (left == nullptr){
			int64_t mid = (node_l + node_r)/2;
			left = new Node(node_l, mid);
			right = new Node(mid+1, node_r);
		}
	}
	void push(){
		check_children();
		left->add_lazy(lazy);
		right->add_lazy(lazy);
		lazy = 0;
	}
	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();
		left->add(l, r, x);
		right->add(l, r, x);
		mn_diff = min(left->mn_diff, 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 );
		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 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 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 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 7 ms 7004 KB Output is correct
7 Correct 7 ms 7772 KB Output is correct
8 Correct 78 ms 61372 KB Output is correct
9 Correct 75 ms 61984 KB Output is correct
10 Correct 61 ms 59540 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1338 ms 516476 KB Output is correct
7 Correct 1135 ms 508100 KB Output is correct
8 Correct 1150 ms 517460 KB Output is correct
9 Runtime error 1206 ms 524288 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 7 ms 7004 KB Output is correct
7 Correct 7 ms 7772 KB Output is correct
8 Correct 78 ms 61372 KB Output is correct
9 Correct 75 ms 61984 KB Output is correct
10 Correct 61 ms 59540 KB Output is correct
11 Correct 1338 ms 516476 KB Output is correct
12 Correct 1135 ms 508100 KB Output is correct
13 Correct 1150 ms 517460 KB Output is correct
14 Runtime error 1206 ms 524288 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -