Submission #946476

#	Time	Username	Problem	Language	Result	Execution time	Memory
946476		infrapolar	Happiness (Balkan15_HAPPINESS)	C++17	60 / 100	3515 ms	524288 KiB

happiness

#include "happiness.h"
#include <cstdint>
#include <algorithm>
#include <functional>
#include <map>
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);
	}


};
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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40