#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
const int U = 1.01e9;
struct Node{
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;
}
};
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 Node{a, b, nullptr, nullptr, 0, 0};
return ret;
}
Node* node_ones(int a = 1, int b = U){
Node* ret = new 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(u->zeros() <= cnt){
cnt -= u->zeros();
return node_ones(u->a, u->b);
}
Node* ret = new 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(u->ones <= cnt){
cnt -= u->ones;
return node_zeros(u->a, u->b);
}
Node* ret = new 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 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 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_sub = 0;
Node* effect = nullptr;
void print(){
cerr << "pre sub: " << pre_sub << "\n";
if(effect) ::print(effect, 0);
cerr << "\n";
}
};
State merge(State now, State old){
int sub = now.pre_sub;
Node* ret = old.effect;
ret = fill_with_zeros(ret, sub);
ret = merge(now.effect, ret);
return State{sub + old.pre_sub, ret};
}
State from_add(int d){
if(d < 0){
return State{-d, node_zeros()};
} else {
Node* ret = node_zeros();
ret = fill_with_ones(ret, d);
assert(!d);
return State{0, 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();
vector<int> ret(n);
for(int i=0; i<n; ++i){
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);
}
//out.print();
}
//cerr << "done\n";
const int ans = query(out.effect, c[i]);
ret[i] = ans;
}
return ret;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
972 KB |
Output is correct |
| 2 |
Correct |
1 ms |
588 KB |
Output is correct |
| 3 |
Correct |
79 ms |
60208 KB |
Output is correct |
| 4 |
Correct |
539 ms |
433040 KB |
Output is correct |
| 5 |
Runtime error |
1520 ms |
1048580 KB |
Execution killed with signal 9 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1341 ms |
1048580 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
24292 KB |
Output is correct |
| 2 |
Runtime error |
1241 ms |
1048580 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
844 KB |
Output is correct |
| 2 |
Correct |
95 ms |
74308 KB |
Output is correct |
| 3 |
Runtime error |
1236 ms |
1048580 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
972 KB |
Output is correct |
| 2 |
Correct |
1 ms |
588 KB |
Output is correct |
| 3 |
Correct |
79 ms |
60208 KB |
Output is correct |
| 4 |
Correct |
539 ms |
433040 KB |
Output is correct |
| 5 |
Runtime error |
1520 ms |
1048580 KB |
Execution killed with signal 9 |
