| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 683368 | Tenis0206 | Abracadabra (CEOI22_abracadabra) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
struct queries
{
int t,poz,cnt;
};
struct Node
{
Node *st, *dr;
int prior, sz;
int val, Min;
};
Node *modfiu(Node *nod, bool care, Node *son)
{
if(care==0)
{
nod -> st = son;
}
else
{
nod -> dr = son;
}
nod -> sz = nod -> st -> sz + 1 + nod -> dr -> sz;
nod -> Min = nod -> val;
nod -> Min = min(nod -> Min, nod->st->Min);
nod -> Min = min(nod -> Min, nod->dr->Min);
return nod;
}
Node *join(Node *st, Node *dr, bool care)
{
if(st==&nil[care])
{
return dr;
}
if(dr==&nil[care])
{
return st;
}
if(st->prior >= dr->prior)
{
return modfiu(st,1,join(st->dr,dr,care));
}
else
{
return modfiu(dr,0,join(st,dr->st,care));
}
}
pair<Node*,Node*> split(Node *nod, int k, bool care)
{
if(nod==&nil[care])
{
return {&nil[care],&nil[care]};
}
if(nod->st->sz>=k)
{
auto t = split(nod->st,k,care);
return {t.first,modfiu(nod,0,t.second)};
}
else
{
auto t = split(nod->dr,k - nod->st->sz - 1,care);
return {modfiu(nod,1,t.first),t.second};
}
}
int get_cnt_first(Node *nod, bool care)
{
if(nod->st == &nil[care])
{
return nod -> sz;
}
return get_cnt_first(nod->st,care);
}
int query(int poz)
{
auto t = split(T,poz-1,0);
auto t2 = split(t,1,0);
int val = t2.first -> val;
T = join(t.first,join(t2.first,t2.second,0),0);
return val;
}
bool next_perm()
{
auto t = split(I,n/2,1);
int cnt = get_cnt_first(t.second,1);
auto t2 = split(t.second,cnt,1);
t2.first -> sz = n / 2 - t.first -> sz;
I = join(t.first,join(t2.first,t2.second,1),1);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for(int i=1; i<=n; i++)
{
cin>>v[i];
}
for(int i=1; i<=m; i++)
{
cin>>q[i].t>>q[i].poz;
q[i].cnt = i;
}
auto cmp = [](queries a, queries b)
{
return a.t < b.t;
};
sort(q+1,q+m+1,cmp);
int first = v[1];
int nr = 0;
for(int i=1; i<=n; i++)
{
if(v[i] > first || i == n / 2 + 1)
{
if(i!=1)
{
I = join(I,new Node{&nil[1],&nil[1],my_rand(),nr,first,0},1);
}
first = v[i];
nr = 0;
}
++nr;
T = join(T,new Node{&nil[0],&nil[0],my_rand(),1,v[i],v[i]},0);
}
int poz = 1;
while(q[poz].t == 0)
{
rez[q[poz].cnt] = query(q[poz].poz);
++poz;
}
for(int t=1;t<=n;t++)
{
bool ok = next_perm();
if(!ok)
{
break;
}
while(poz<=m && q[poz].t==t)
{
rez[q[poz].cnt] = query(q[poz].poz);
}
}
for(int i=poz;i<=m;i++)
{
rez[q[i].cnt] = query(q[i].poz);
}
for(int i=1;i<=m;i++)
{
cout<<rez[i]<<'\n';
}
return 0;
}