Submission #807573

#	Time	Username	Problem	Language	Result	Execution time	Memory
807573		HaroldVemeno	Abracadabra (CEOI22_abracadabra)	C++17	10 / 100	3065 ms	33264 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];

struct Node {
    int v;
    int s = 1;
    int p = rand();
    Node* l = nullptr;
    Node* r = nullptr;
    Node* c = 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 << "| ";
            if(pos == 2)  o << "c ";
            o << ",-o\n";
        } else {
            if(pos == -1) l->print(o, bef + "  ", -1);
            if(pos == 1)  l->print(o, bef + "| ", -1);
            if(pos == 2) l->print(o, bef + "c ", -1);
            if(pos == 0)  l->print(o, bef, -1);
        }
        o << bef;
        if(pos == -1) o << ",-";
        if(pos == 1)  o << "`-";
        if(pos == 2)  o << "c-";
        o << "(v: " << v << ", p: " << p << ", s:" << s << ")\n";
        if(c) {
            if(pos == -1) c->print(o, bef + "| | ", 2);
            if(pos == 1) c->print(o, bef + "  | ", 2);
            if(pos == 2) c->print(o, bef + "  | ", 2);
            if(pos == 0) c->print(o, bef + "| ", 2);
        }
        if(r == nullptr) {
            o << bef;
            if(pos == -1) o << "| ";
            if(pos == 1)  o << "  ";
            if(pos == 2)  o << "  ";
            o << "`-o\n";
        } else {
            if(pos == -1) r->print(o, bef + "| ", 1);
            if(pos == 1)  r->print(o, bef + "  ", 1);
            if(pos == 2)  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;
    }

};

Node buf[200000];

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

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

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};
    }
}

Node* merge2(Node* a, Node* b) {
    if(!a) return b;
    if(!b) return a;
    if(b->p > a->p) swap(a, b);
    auto [l, r] = splitbyv(b, a->v);
    a->l = merge2(l, a->l);
    a->r = merge2(r, a->r);
    pull(a);
    return a;
}

Node* merge(Node* a, Node* b) {
    if(!a) return b;
    if(!b) return a;
    if(a->s > b->s) swap(a, b);
    b = merge(a->l, b);
    a->l = nullptr;
    b = merge(a->r, b);
    a->r = nullptr;
    pull(a);
    auto [l, r] = splitbyv(b, a->v);
    b = concat(l, concat(a, r));
    return b;
}

struct SplitRes {
    Node* l;
    Node* m;
    Node* r;
};

SplitRes splitons(Node* a, int s) {
    D(s)
    D(a)
    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) + size(a->c) + 1) {
        auto[l, m, r] = splitons(a->r, s - size(a->c) - size(a->l) - 1 );
        a->r = l;
        pull(a);
        return {a, m, r};
    } else {
        auto[l, m, r] = splitons(a->c, s - size(a->l) - 1);
        m = concat(m, r);
        a->c = l;
        auto ar = a->r;
        a->r = nullptr;
        pull(a);
        return {a, m, ar};
    }
}


int valuebys(Node* a, int s) {
    D(size(a))
    if(s < size(a->l)) {
        return valuebys(a->l, s);
    } else if(s == size(a->l)) {
        return a->v;
    } else if(s < size(a->l) + 1 + size(a->c)) {
        return valuebys(a->c, s - size(a->l) - 1);
    } else {
        return valuebys(a->r, s - size(a->l) - 1 - size(a->c));
    }
}

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

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

    srand(4994040);

    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;});

    vector<Node*> trs;
    for(int i = n-1; i >= 0; --i) {
        Node* tr = buf+i;
        tr->v = as[i];
        tr->s = 1;
        tr->p = rand();
        while(!trs.empty() && trs.back()->v < tr->v) {
            tr->c = concat(tr->c, trs.back());
            trs.pop_back();
        }
        pull(tr);
        trs.push_back(tr);
    }
    Node* tr = nullptr;
    for(Node* t : trs) {
        tr = concat(t, tr);
    }
    trs.clear();
    D(tr);
    D(size(tr));

    int t = 0;
    bool changed = true;
    for(int i = 0; i < q; ++i) {
        D(i)
        while(changed && qs[i].t > t) {
            D(t)
            auto [l, m, r] = splitons(tr, n/2);
            if(m == nullptr) changed = false;
            D(l)
            D(m)
            D(r)
            l = merge(l, m);
            D(l)
            tr = concat(l, r);
            D(tr)
            ++t;
        }
        D(t)
        qs[i].res = valuebys(tr, qs[i].ind);
    }


    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: 10 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25