#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
const int U = 1.01e9;
struct Node{
int a, b;
Node *l, *r;
int me;
int ones;
/*int a = -2, b = -2;
Node *l = nullptr, *r = nullptr;
int me = -1;
int ones = -2;*/
int len() const {
return b-a;
}
int zeros() const {
return len() - ones;
}
int m() const {
return a + len()/2;
}
void recalc(){
if(me == 0) ones = 0;
else if(me == 1) ones = len();
else ones = r->ones + l->ones;
}
};
const int SIZE = 2e7;
int pool_back = 0;
Node pool[SIZE];
Node* get_free_node(){
return pool + (pool_back++);
}
int query(Node* u, int x){
if(x < u->a) return 0;
if(x >= u->b){
return u->ones;
}
if(u->me == 0){
return 0;
}
if(u->me == 1){
return x - u->a + 1;
}
return query(u->l, x) + query(u->r, x);
}
Node* node_zeros(int a = 1, int b = U){
Node* ret = new (get_free_node()) Node{a, b, nullptr, nullptr, 0, 0};
return ret;
}
Node* node_ones(int a = 1, int b = U){
Node* ret = new (get_free_node()) Node{a, b, nullptr, nullptr, 1, b-a};
return ret;
}
Node* node_fixed_val(int val, int a = 1, int b = U){
if(val == 0) return node_zeros(a, b);
if(val == 1) return node_ones(a, b);
assert(0);
return nullptr;
}
void check_split(Node*u){
if(u->me != -1){
u->l = node_fixed_val(u->me, u->a, u->m());
u->r = node_fixed_val(u->me, u->m(), u->b);
u->me = -1;
} else {
assert(u->l && u->r);
}
}
int index_of_last_one(Node*u){
if(u->me == 0) return u->a-1;
if(u->me == 1){
return u->b - 1;
}
assert(u->l && u->r);
if(u->r->ones){
return index_of_last_one(u->r);
} else {
return index_of_last_one(u->l);
}
}
Node* fill_with_ones(Node*u, int &cnt){
if(!cnt) return u;
if(u->zeros() <= cnt){
cnt -= u->zeros();
return node_ones(u->a, u->b);
}
Node* ret = new (get_free_node()) Node(*u);
check_split(ret);
ret->l = fill_with_ones(ret->l, cnt);
if(cnt){
ret->r = fill_with_ones(ret->r, cnt);
}
ret->recalc();
return ret;
}
Node* fill_with_zeros(Node*u, int &cnt){
if(!cnt) return u;
if(u->ones <= cnt){
cnt -= u->ones;
return node_zeros(u->a, u->b);
}
Node* ret = new (get_free_node()) Node(*u);
check_split(ret);
ret->l = fill_with_zeros(ret->l, cnt);
if(cnt){
ret->r = fill_with_zeros(ret->r, cnt);
}
ret->recalc();
return ret;
}
Node* merge_rec_2(Node*now, int old){
Node*ret = new (get_free_node()) Node(*now);
if(ret->me == 1){
return ret;
}
assert(ret->me != 0);
if(now->r->ones){
ret->r = merge_rec_2(now->r, old);
ret->recalc();
return ret;
} else{
ret->r = node_fixed_val(old, ret->r->a, ret->r->b);
ret->l = merge_rec_2(now->l, old);
ret->recalc();
return ret;
}
}
Node* merge_rec(Node*now, Node*old){
if(old->me != -1){
return merge_rec_2(now, old->me);
}
Node*ret = new (get_free_node()) Node(*now);
if(ret->me == 1){
return ret;
}
assert(ret->me != 0);
if(now->r->ones){
ret->r = merge_rec(now->r, old->r);
ret->recalc();
return ret;
} else{
ret->r = old->r;
ret->l = merge_rec(now->l, old->l);
ret->recalc();
return ret;
}
}
void print(Node* u, int d){
cerr << setw(2*d) << u->a << " " << u->b << " : " << u->me << "\n";
if(u->l){
print(u->l, d+1);
}
if(u->r){
print(u->r, d+1);
}
}
Node* merge(Node* now, Node* old){
if(!now->ones){
return old;
}
int fill_cnt = index_of_last_one(now);
Node* ret = fill_with_ones(old, fill_cnt);
ret = merge_rec(now, ret);
return ret;
}
struct State{
int pre_add = 0;
int pre_sub = 0;
Node* effect = nullptr;
void print(){
cerr << "pre add: " << pre_add << "\n";
cerr << "pre sub: " << pre_sub << "\n";
if(effect) ::print(effect, 0);
cerr << "\n";
}
};
State merge(State now, State old){
const int diff = now.effect->ones - now.pre_sub + old.effect->ones - old.pre_sub;
/*if(!now.effect->ones && diff <= 0){
// we become negative
return State{max(old.pre_add, now.pre_add-old.pre_sub+old.effect->ones), -diff, node_zeros()};
}*/
// we become positive
int add = now.pre_add;
int sub = now.pre_sub + now.pre_add;
Node* ret = old.effect;
ret = fill_with_ones(ret, add);
ret = fill_with_zeros(ret, sub);
ret = merge(now.effect, ret);
//return State{old.pre_add, sub + old.pre_sub, ret};
return State{max(old.pre_add, now.pre_add-old.pre_sub+old.effect->ones), sub + old.pre_sub, ret};
}
State from_add(int d){
if(d < 0){
return State{0, -d, node_zeros()};
} else {
Node* ret = node_zeros();
ret = fill_with_ones(ret, d);
assert(!d);
return State{0, 0, ret};
}
}
const State ZERO = from_add(0);
struct Segment_Tree{
Segment_Tree(int n_) : N(n_), nodes(4*N, ZERO){
}
void push_me(int n){
nodes[2*n] = merge(nodes[n], nodes[2*n]);
nodes[2*n+1] = merge(nodes[n], nodes[2*n+1]);
nodes[n] = ZERO;
}
void u(int n, int a, int b, int l, int r, State s){
if(r < a || l > b){
return;
}
if(l <= a && b <= r){
nodes[n] = merge(s, nodes[n]);
return;
}
push_me(n);
u(2*n, a, (a+b)/2, l, r, s);
u(2*n+1, (a+b)/2+1, b, l, r, s);
}
void u(int l, int r, State s){
u(1, 0, N-1, l, r, s);
}
template<typename T>
void push(int n, int a, int b, T fun){
if(a == b){
fun(a, nodes[n]);
return;
}
push_me(n);
push(2*n, a, (a+b)/2, fun);
push(2*n+1, (a+b)/2+1, b, fun);
}
template<typename T>
void push(T fun){
push(1, 0, N-1, fun);
}
int N;
vector<State> nodes;
vector<int> out;
};
vector<int> distribute_candies_brute(vector<int> c, vector<int> l,
vector<int> r, vector<int> v) {
const int n = c.size();
const int q = l.size();
vector<int> ret(n);
for(int i=0; i<n; ++i){
pool_back = 0;
State out = from_add(0);
for(int j=0; j<q; ++j){
if(l[j] <= i && i <= r[j]){
out = merge(from_add(v[j]), out);
}
//if(i == 0) out.print();
}
//cerr << "done\n";
const int ans = query(out.effect, c[i]);
ret[i] = ans;
}
return ret;
}
vector<int> distribute_candies(vector<int> c, vector<int> l,
vector<int> r, vector<int> v) {
auto real = distribute_candies_brute(c, l, r, v);
const int n = c.size();
const int q = l.size();
vector<int> ret(n);
for(int i=0; i<n; ++i){
pool_back = 0;
State out = from_add(0);
for(int j=q-1; j>=0; --j){
if(l[j] <= i && i <= r[j]){
out = merge(out, from_add(v[j]));
}
if(i == 11) out.print();
}
//cerr << "done\n";
const int ans = query(out.effect, c[i]);
ret[i] = ans;
cerr << c[i] << " : " << ret[i] << " " << real[i] << "\n";
//assert(ret[i] == real[i]);
}
return ret;
}
/*vector<int> distribute_candies(vector<int> c, vector<int> l,
vector<int> r, vector<int> v) {
const int n = c.size();
const int q = l.size();
Segment_Tree st(n);
for(int j=0; j<q; ++j){
st.u(l[j], r[j], from_add(v[j]));
}
vector<int> ret(n);
st.push([&](int i, State &s){
const int ans = query(s.effect, c[i]);
ret[i] = ans;
});
return ret;
}*/
Compilation message
candies.cpp: In function 'State merge(State, State)':
candies.cpp:188:15: warning: unused variable 'diff' [-Wunused-variable]
188 | const int diff = now.effect->ones - now.pre_sub + old.effect->ones - old.pre_sub;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
39 ms |
10040 KB |
Output is correct |
| 4 |
Correct |
4977 ms |
34760 KB |
Output is correct |
| 5 |
Execution timed out |
5063 ms |
20764 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5093 ms |
29184 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
332 KB |
Output is correct |
| 2 |
Execution timed out |
5085 ms |
148940 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
48 ms |
404 KB |
Output is correct |
| 3 |
Execution timed out |
5129 ms |
633596 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
39 ms |
10040 KB |
Output is correct |
| 4 |
Correct |
4977 ms |
34760 KB |
Output is correct |
| 5 |
Execution timed out |
5063 ms |
20764 KB |
Time limit exceeded |
