Submission #946561

#	Time	Username	Problem	Language	Result	Execution time	Memory
946561		infrapolar	Happiness (Balkan15_HAPPINESS)	C++17	100 / 100	1556 ms	446100 KiB

happiness

#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 (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: 40 / 40