Submission #807314

#	Time	Username	Problem	Language	Result	Execution time	Memory
807314		HaroldVemeno	Abracadabra (CEOI22_abracadabra)	C++17	0 / 100	391 ms	32652 KiB

Main

#include <bits/stdc++.h>

#ifdef GUDEB
    #define D(x) cerr << #x << ": " << (x) << '\n';
    #define ifdeb if(true)
#else
    #define D(x) ;
    #define ifdeb if(false)
#endif

#define all(x) begin(x), end(x)

using namespace std;
using ull = unsigned long long;
using ll = long long;
// #define int ll;

int as[200000];
int nas[200000];

struct Node {
    int b;
    int e;
    int v;
    int s = e - b;
    int p = rand();
    Node* l = nullptr;
    Node* r = nullptr;

    void print(ostream& o, string bef = string{}, int pos = 0) const {
        if(l == nullptr) {
            o << bef;
            if(pos == -1) o << "  ";
            if(pos == 1)  o << "| ";
            o << ",-o\n";
        } else {
            if(pos == -1) l->print(o, bef + "  ", -1);
            if(pos == 1)  l->print(o, bef + "| ", -1);
            if(pos == 0)  l->print(o, bef, -1);
        }
        o << bef;
        if(pos == -1) o << ",-";
        if(pos == 1)  o << "`-";
        o << "(v: " << v << ", p: " << p << ", s:" << s << ", b: " << b << ", e: " << e << ")\n";
        o << bef;
        if(pos == -1) o << "| | ";
        if(pos == 1)  o << "  | ";
        for(int i = b; i < e; ++i) o << nas[i] << ' ';
        o << '\n';
        if(r == nullptr) {
            o << bef;
            if(pos == -1) o << "| ";
            if(pos == 1)  o << "  ";
            o << "`-o\n";
        } else {
            if(pos == -1) r->print(o, bef + "| ", 1);
            if(pos == 1)  r->print(o, bef + "  ", 1);
            if(pos == 0)  r->print(o, bef, 1);
        }

    }

    friend ostream& operator<< (ostream& o, const Node* a) {
        o << '\n';
        if(!a) o << "o\n";
        else a->print(o);
        return o;
    }

};


int size(Node* a) {
    return a?a->s:0;
}

void pull(Node* a) {
    if(a) {
        a->s = a->e - a->b;
        a->s += size(a->r);
        a->s += size(a->l);
    }
}

Node* concat(Node* a, Node* b) {
    if(!a) return b;
    if(!b) return a;
    if(a->p > b->p) {
        a->r = concat(a->r, b);
        pull(a);
        return a;
    } else {
        b->l = concat(a, b->l);
        pull(b);
        return b;
    }
}

pair<Node*, Node*> splitbyv(Node* a, int v) {
    if(!a) return {a, a};
    if(a->v < v) {
        auto [rl, rr] = splitbyv(a->r, v);
        a->r = rl;
        pull(a);
        return {a, rr};
    } else {
        auto [ll, lr] = splitbyv(a->l, v);
        a->l = lr;
        pull(a);
        return {ll, a};
    }
}

array<Node*, 3> splitons(Node* a, int s) {
    if(!a) return {a, a, a};
    if( s <= size(a->l) ) {
        auto[l, m, r] = splitons(a->l, s);
        a->l = r;
        pull(a);
        return {l, m, a};
    } else if(s >= size(a->l) + a->e - a->b ) {
        auto[l, m, r] = splitons(a->r, s - size(a->l) - a->e + a->b);
        a->r = l;
        pull(a);
        return {a, m, r};
    } else {
        Node* l = a->l;
        Node* r = a->r;
        a->l = nullptr;
        a->r = nullptr;
        pull(a);
        return {l, a, r};
    }
}


int valuebys(Node* a, int s) {
    D(size(a))
    if(s < size(a->l)) {
        return valuebys(a->l, s);
    } else if( size(a->l) + a->e - a->b <= s) {
        return valuebys(a->r, s - size(a->l) - a->e + a->b);
    } else {
        return nas[a->b + s - size(a->l)];
    }
}

Node* first(Node* a) {
    if(!a) return a;
    if(a->l) return first(a->l);
    return a;
}

Node* last(Node* a) {
    if(!a) return a;
    if(a->r) return last(a->r);
    return a;

}

struct Q {
    int t;
    int ind;
    int i;
    int res;
};

void solve() {
    int n, q;
    cin >> n >> q;

    vector<Q> qs(q);
    for(int i = 0; i < n; ++i) {
        cin >> as[i];
    }
    for(int i = 0; i < q; ++i) {
        cin >> qs[i].t >> qs[i].ind;
        --qs[i].ind;
        qs[i].i = i;
    }
    sort(all(qs), [](Q a, Q b){return a.t < b.t;});

    int i = 0;
    int t = 0;
    while(qs[i].t == 0) {
        qs[i].res = as[qs[i].ind];
        ++i;
    }

    Node* tr = nullptr;

    {
        Node* tb = nullptr;
        int o = 0;
        int i1 = 0;
        int i2 = n/2;
        while(i1 < n/2 && i2 < n) {
            if(as[i1] < as[i2]) {
                nas[o] = as[i1];
                ++o;
                ++i1;
            } else {
                nas[o] = as[i2];
                ++o;
                ++i2;
            }
        }
        while(i1 < n/2) {
            nas[o] = as[i1];
            ++o;
            ++i1;
        }
        while(i2 < n) {
            nas[o] = as[i2];
            ++o;
            ++i2;
        }
        tb = new Node{0, 1, nas[0]};
        ifdeb {
            for(int i = 0; i < n; ++i)
                cerr << nas[i] << ' ';
            cerr << '\n';
        }

        for(int j = 1; j < n; ++j) {
            if(nas[j] <= nas[j-1]) {
                ++tb->e;
            } else {
                pull(tb);
                D(size(tb))
                tr = concat(tr, tb);
                tb = new Node{j, j+1, nas[j]};
            }
        }
        tr = concat(tr, tb);
    }
    ++t;
    bool changed = true;


    while(i < q) {
        D(i)
        while(t < qs[i].t && changed) {
            changed = false;
            D(size(tr))
            auto[l, m, r]  = splitons(tr, n/2);
            D(l);
            D(r);
            D(size(l))
            D(size(m))
            D(size(r))
            if(m != nullptr) {
                Node* ml = m;
                Node* mr = new Node{n/2 - size(l) + m->b, m->e, nas[n/2 - size(l) + m->b]};
                ml->e = n/2 - size(l) + m->b;
                ml->s = m->e - m->b;
                l = concat(l, ml);
                r = concat(mr, r);
            }
            D(l);
            D(r);
            Node* fstr = first(r);
            Node* lstl = last(l);
            while(l && r && fstr->v < lstl->v) {
                changed = true;
                D(l)
                D(r)
                auto [af, b, nr] = splitons(r, fstr->e - fstr->b);
                D(af)
                D(b)
                D(nr)
                assert(!b);
                auto [ll, lr] = splitbyv(l, af->v);
                l = concat(ll, concat(af, lr));
                r = nr;
                fstr = first(r);

            }
            tr = concat(l,  r);
            assert(size(tr) == n);
            ++t;
            D(t);
            D(tr);
        }
        qs[i].res = valuebys(tr, qs[i].ind);
        ++i;
    }

    D(tr)

    sort(all(qs), [](Q a, Q b){return a.i < b.i;});
    for(auto q : qs) cout << q.res << '\n';
    return;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << setprecision(20);

    solve();
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25