Submission #435671

#	Time	Username	Problem	Language	Result	Execution time	Memory
435671		dacin21	사탕 분배 (IOI21_candies)	C++17	0 / 100	1726 ms	1048580 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 = 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(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};
    }
}
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(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;
}

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