oj.uz

Submission #435645

# Submission time Handle Problem Language Result Execution time Memory
435645 2021-06-23T14:08:19 Z dacin21 Distributing Candies (IOI21_candies) C++17
0 / 100
 1390 ms 1048580 KB 
#include "candies.h"

#include <bits/stdc++.h>
using namespace std;

const int U = 1.01e9;
struct Node{
    int a = -2, b = -2;
    int me = -1;
    Node *l = nullptr, *r = nullptr;
    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, 0, nullptr, nullptr, 0};
    return ret;
}
Node* node_ones(int a = 1, int b = U){
    Node* ret = new Node{a, b, 1, nullptr, nullptr, b-a};
    return ret;
}
void check_split(Node*u){
    if(u->me == 0){
        u->l = node_zeros(u->a, u->m());
        u->r = node_zeros(u->m(), u->b);
        u->me = -1;
    } else if(u->me == 1){
        u->l = node_ones(u->a, u->m());
        u->r = node_ones(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(Node*now, Node*old){
    if(old->me != -1){ // TODO: optimize
        old = new Node(*old);
        check_split(old);
    }
    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;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 972 KB Output is correct
2 Correct 2 ms 716 KB Output is correct
3 Correct 78 ms 65668 KB Output is correct
4 Correct 611 ms 466144 KB Output is correct
5 Runtime error 1390 ms 1048580 KB Execution killed with signal 9

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1258 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 25164 KB Output is correct
2 Runtime error 1202 ms 1048580 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 972 KB Output is correct
2 Correct 104 ms 80060 KB Output is correct
3 Runtime error 1271 ms 1048580 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 972 KB Output is correct
2 Correct 2 ms 716 KB Output is correct
3 Correct 78 ms 65668 KB Output is correct
4 Correct 611 ms 466144 KB Output is correct
5 Runtime error 1390 ms 1048580 KB Execution killed with signal 9