Submission #831724

#	Time	Username	Problem	Language	Result	Execution time	Memory
831724		QwertyPi	Abracadabra (CEOI22_abracadabra)	C++14	100 / 100	799 ms	42436 KiB

Main

#include <bits/stdc++.h>

using namespace std;

vector<int> shuffle(vector<int> a){
    int n = a.size();
    vector<int> a1(a.begin(), a.begin() + n / 2), a2(a.begin() + n / 2, a.end());
    a1.push_back(1 << 30); a2.push_back(1 << 30);
    int l = 0, r = 0;
    vector<int> b;
    for(int i = 0; i < n; i++){
        if(a1[l] < a2[r]) b.push_back(a1[l++]);
        else b.push_back(a2[r++]);
    }
    return b;
}

const int MAXN = 2e5 + 11;
const int MAXQ = 1e6 + 11;
int ans[MAXQ];

struct query{
    int t, i, id;
    bool operator< (const query& o) const {
        return t < o.t;
    }
};

struct BIT{
    int bit[MAXN];
    void add(int p, int v){ p++; for(int i = p; i < MAXN; i += i & -i) bit[i] += v; }
    int qry(int p){ p++; int r = 0; for(int i = p; i; i -= i & -i) r += bit[i]; return r; }
    int bs(int v){ int r = 0, s = 0; for(int j = 19; j >= 0; j--) if(r + (1 << j) < MAXN && s + bit[r + (1 << j)] < v) s += bit[r + (1 << j)], r += (1 << j); return r; }
} bit;

int p[MAXN];

vector<int> a;
int n, q;
int nxt[MAXN];

void simulate_shuffle(){
    int pos = bit.bs(n / 2);
    int v1 = bit.qry(pos), v2 = bit.qry(pos - 1);
    if(v1 == n / 2) return;
    int x = p[pos] + (n / 2 - v2);
    vector<int> split; split.push_back(x);
    while(nxt[x] < p[pos] + (v1 - v2))
        x = nxt[x], split.push_back(x);
    split.push_back(p[pos] + (v1 - v2));

    bit.add(pos, n / 2 - v1);
    for(int i = 0; i + 1 < split.size(); i++){
        bit.add(a[split[i]], split[i + 1] - split[i]);
        p[a[split[i]]] = split[i];
    }
}

int calculate_position(int i){
    int pos = bit.bs(i);
    int ri = bit.qry(pos - 1);
    return a[p[pos] + (i - (ri + 1))];
}

int32_t main(){
    cin >> n >> q;
    for(int i = 0; i < n; i++){
        int v; cin >> v; a.push_back(v);
    }

    vector<query> Q;
    for(int id = 0; id < q; id++){
        int t, i; cin >> t >> i; Q.push_back({t, i, id});
    }
    sort(Q.begin(), Q.end());

    for(auto q : Q){
        if(q.t == 0) ans[q.id] = a[q.i - 1];
        else break;
    }

    a = shuffle(a);
    a.push_back(1 << 30);
    vector<int> geq;
    geq.push_back(n);
    for(int i = n - 1; i >= 0; i--){
        while(!geq.empty() && a[geq.back()] < a[i]) geq.pop_back();
        nxt[i] = geq.back();
        geq.push_back(i);
    }

    int ct = 1;

    vector<int> idx;
    idx.push_back(0);
    for(int i = 1; i < n; i++){
        if(a[idx.back()] < a[i]) idx.push_back(i);
    }
    idx.push_back(n);
    for(int i = 0; i + 1 < idx.size(); i++){
        bit.add(a[idx[i]], idx[i + 1] - idx[i]);
        p[a[idx[i]]] = idx[i];
    }

    for(auto q : Q){
        if(q.t == 0) continue;
        while(ct < q.t && ct < n) simulate_shuffle(), ct++;
        ans[q.id] = calculate_position(q.i);
    }
    for(int i = 0; i < q; i++){
        cout << ans[i] << '\n';
    }
}

Compilation message (stderr)

Main.cpp: In function 'void simulate_shuffle()':
Main.cpp:53:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i = 0; i + 1 < split.size(); i++){
      |                    ~~~~~~^~~~~~~~~~~~~~
Main.cpp: In function 'int32_t main()':
Main.cpp:100:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     for(int i = 0; i + 1 < idx.size(); i++){
      |                    ~~~~~~^~~~~~~~~~~~

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