Submission #435652

#	Time	Username	Problem	Language	Result	Execution time	Memory
435652		dacin21	Distributing Candies (IOI21_candies)	C++17	3 / 100	5107 ms	944256 KiB

candies

#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 = 3e7;
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(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(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_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){
        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);
            }
            //out.print();
        }
        //cerr << "done\n";
        const int ans = query(out.effect, c[i]);
        ret[i] = ans;
    }
    return ret;
}

• Subtask 1: 3 / 3
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33