#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 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++;
}
}
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 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, 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);
root.add(0, tree_size, inf, 0, tree_size);
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;
| ^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
