Submission #830562

#	Time	Username	Problem	Language	Result	Execution time	Memory
830562		peteza	Abracadabra (CEOI22_abracadabra)	C++14	0 / 100	284 ms	48764 KiB

Main

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

mt19937 mt(3453);

int n, q;
int arr[200005], poss[200005], ans[1000005];
int t, pos, idx;
bool vis[200005];
vector<pair<int, int>> qrs[200005];

struct node {
    node *l, *r;
    long long prior;
    int val, sz;
    node(int x):val(x),prior(mt()),l(0),r(0),sz(1){}
} *root;

int getsz(node*&c){return c?c->sz:0;}
void updsz(node*&c){if(c)c->sz=getsz(c->l)+getsz(c->r)+1;}

node* mg(node*a, node*b) {
    if(!a || !b) return a ? a : b;
    if(a->prior > b->prior) {
        a->r = mg(a->r, b);
        updsz(a);
        return a;
    } else {
        b->l = mg(a, b->l);
        updsz(b);
        return b;
    }
}

void inord(node*&cur) {
    if(!cur) return;
    inord(cur->l);
    cout << cur->val << ' ';
    inord(cur->r);
}

int getval(node*&cur, int idx) {
    if(idx == getsz(cur->l)) return cur->val;
    if(idx <= getsz(cur->l)) return getval(cur->l, idx);
    return getval(cur->r, idx-getsz(cur->l)-1);
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> q;
    for(int i=1;i<=n;i++) cin >> arr[i], poss[arr[i]] = i;
    for(int i=0;i<q;i++) {
        cin >> t >> pos;
        t = min(t, n); pos--;
        if(t==0) ans[i] = arr[pos+1];
        else qrs[t].emplace_back(pos, i);
    }
    for(int i=n;i>=1;i--) {
        if(vis[poss[i]]) continue;
        node* newr = 0;
        for(int j=poss[i];j!=n+1&&(j!=n/2+1 || poss[i]==n/2+1)&&!vis[j];j++) {
            vis[j] = 1;
            newr = mg(newr, new node(arr[j]));
        }
        root = mg(newr, root);
    }
    //inord(root);
    for(int i=1;i<=n;i++) {
        for(auto e:qrs[i]) {
            tie(pos, idx) = e;
            ans[idx] = getval(root, pos);

        }        
    }

    for(int i=0;i<q;i++) cout << ans[i] << '\n';
}

Compilation message (stderr)

Main.cpp: In constructor 'node::node(int)':
Main.cpp:15:9: warning: 'node::val' will be initialized after [-Wreorder]
   15 |     int val, sz;
      |         ^~~
Main.cpp:14:15: warning:   'long long int node::prior' [-Wreorder]
   14 |     long long prior;
      |               ^~~~~
Main.cpp:16:5: warning:   when initialized here [-Wreorder]
   16 |     node(int x):val(x),prior(mt()),l(0),r(0),sz(1){}
      |     ^~~~
Main.cpp:14:15: warning: 'node::prior' will be initialized after [-Wreorder]
   14 |     long long prior;
      |               ^~~~~
Main.cpp:13:11: warning:   'node* node::l' [-Wreorder]
   13 |     node *l, *r;
      |           ^
Main.cpp:16:5: warning:   when initialized here [-Wreorder]
   16 |     node(int x):val(x),prior(mt()),l(0),r(0),sz(1){}
      |     ^~~~

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