Submission #820599

#	Time	Username	Problem	Language	Result	Execution time	Memory
820599		dashka	Abracadabra (CEOI22_abracadabra)	C++14	100 / 100	672 ms	47188 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 nbe[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 << as[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};
    }
}
 
Node* merge(Node* a, Node* b) {
    if(!a) return b;
    if(!b) return a;
    if(a->p < b->p) swap(a, b);
    auto[l, r] = splitbyv(b, a->v);
    a->l = merge(a->l, l);
    a->r = merge(a->r, r);
    pull(a);
    return 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 as[a->b + s - size(a->l)];
    }
}
 
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;});
 
    // value -> index
    vector<int> st;
    for(int i = n-1; i >= 0; --i) {
        while(!st.empty() && as[st.back()] < as[i]) {
            st.pop_back();
        }
        if(st.empty()) nbe[i] = n;
        else nbe[i] = st.back();
        st.push_back(i);
    }
 
    int i = 0;
    int t = 0;
 
    Node* tr = nullptr;
    for(int i = 0; i < n; i = nbe[i]) {
        tr = concat(tr, new Node{i, nbe[i], as[i]});
    }
    D(tr)
    bool changed = true;
 
    for(int i = 0; i < q; ++i) {
        while(t < qs[i].t && changed) {
            auto[l, m, r] = splitons(tr, n/2);
            D(l)
            D(m)
            D(r)
            if(m == nullptr) {
                changed = false;
                tr = concat(l, r);
                break;
            }
            pull(m);
            Node* mrg = nullptr;
            for(int i = m->b + n/2 - size(l); i < m->e; i = nbe[i]) {
                mrg = concat(mrg, new Node{i, min(nbe[i], m->e), as[i]});
            }
            m->e = m->b + n/2 - size(l);
            pull(m);
            l = merge(l, mrg);
            tr = concat(l, concat(m, r));
            D(tr)
            assert(size(tr) == n);
            ++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();
}

Compilation message (stderr)

Main.cpp: In function 'std::pair<Node*, Node*> splitbyv(Node*, int)':
Main.cpp:102:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  102 |         auto [rl, rr] = splitbyv(a->r, v);
      |              ^
Main.cpp:107:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  107 |         auto [ll, lr] = splitbyv(a->l, v);
      |              ^
Main.cpp: In function 'Node* merge(Node*, Node*)':
Main.cpp:118:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  118 |     auto[l, r] = splitbyv(b, a->v);
      |         ^
Main.cpp: In function 'std::array<Node*, 3> splitons(Node*, int)':
Main.cpp:129:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  129 |         auto[l, m, r] = splitons(a->l, s);
      |             ^
Main.cpp:134:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  134 |         auto[l, m, r] = splitons(a->r, s - size(a->l) - a->e + a->b);
      |             ^
Main.cpp: In function 'void solve()':
Main.cpp:205:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  205 |             auto[l, m, r] = splitons(tr, n/2);
      |                 ^
Main.cpp:193:9: warning: unused variable 'i' [-Wunused-variable]
  193 |     int i = 0;
      |         ^

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