| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 683823 | 2023-01-19T12:14:17 Z | Tenis0206 | Abracadabra (CEOI22_abracadabra) | C++11 | 7 ms | 596 KB |
#include <bits/stdc++.h>
using namespace std;
struct queries
{
int t,poz,cnt;
};
struct Node
{
Node *st, *dr;
int prior, sz;
int val, Max;
};
int n,m;
int v[100005];
queries q[1000005];
Node nil[2];
Node *T = &nil[0];
Node *I = &nil[1];
int rez[1000005];
mt19937 my_rand(time(NULL));
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 -> Max = nod -> val;
nod -> Max = max(nod -> Max, nod->st->Max);
nod -> Max = max(nod -> Max, nod->dr->Max);
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};
}
}
pair<Node*,Node*> split_by_val(Node *nod, int val, bool care)
{
if(nod==&nil[care])
{
return {&nil[care],&nil[care]};
}
if(nod->st->Max > val)
{
auto t = split(nod->st,val,care);
return {t.first,modfiu(nod,0,t.second)};
}
else
{
auto t = split(nod->dr,val,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(Node *nod, int poz)
{
auto t = split(nod,poz-1,0);
auto t2 = split(t.second,1,0);
int val = t2.first -> val;
T = join(t.first,join(t2.first,t2.second,0),0);
return val;
}
int find_new_poz(int val)
{
if(I->Max==val)
{
return I -> sz;
}
auto t = split_by_val(I,val,1);
int rez = t.first -> sz - 1;
I = join(t.first,t.second,1);
return rez;
}
void debug()
{
for(int i=1;i<=n;i++)
{
cerr<<query(T,i)<<' ';
}
cerr<<'\n';
}
/// 1 2 3 4 5 6
bool next_perm()
{
auto t = split(I,n/2,1);
int first = t.first -> sz + 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);
auto pref = split(T,n/2,0);
auto buc = split(pref.second,first + cnt - 1 - (n / 2),0);
/// pref.first = 1 - n / 2;
/// buc.first = bucata mutata
/// buc.second = sufixul sirului
int poz = n / 2 + 1;
bool ok = false;
while(poz<=first+cnt-1)
{
int val = query(buc.first,1);
pair<Node*,Node*> aux;
if(buc.first -> Max == val)
{
aux.first = buc.first;
aux.second = &nil[0];
}
else
{
aux = split_by_val(buc.first,val,0);
}
int new_poz = find_new_poz(val);
if(new_poz+1!=poz)
{
ok = true;
}
t = split(I,new_poz,1);
I = join(t.first,join(new Node{&nil[1],&nil[1],my_rand(),aux.first -> sz,val,val},t.second,1),1);
t = split(pref.first,new_poz,0);
poz += aux.first -> sz;
pref.first = join(t.first,join(aux.first,t.second,0),0);
buc.first = aux.second;
}
T = join(pref.first,join(buc.first,buc.second,0),0);
debug();
return ok;
}
void first_perm()
{
vector<int> aux;
int st = 1;
int dr = n / 2 + 1;
while(st<=n/2 && dr<=n)
{
if(v[st]<v[dr])
{
aux.push_back(v[st++]);
}
else
{
aux.push_back(v[dr++]);
}
}
while(st<=n/2)
{
aux.push_back(v[st++]);
}
while(dr<=n)
{
aux.push_back(v[dr++]);
}
for(int i=1;i<=n;i++)
{
v[i] = aux[i - 1];
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
freopen("nr.in","r",stdin);
freopen("nr.out","w",stdout);
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 poz = 1;
while(q[poz].t == 0)
{
rez[q[poz].cnt] = v[q[poz].poz];
++poz;
}
first_perm();
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,first},1);
}
first = v[i];
nr = 0;
}
++nr;
T = join(T,new Node{&nil[0],&nil[0],my_rand(),1,v[i],v[i]},0);
}
for(int t=1; t<=n; t++)
{
while(poz<=m && q[poz].t==t)
{
rez[q[poz].cnt] = query(T,q[poz].poz);
++poz;
}
bool ok = next_perm();
if(!ok)
{
break;
}
}
for(int i=poz; i<=m; i++)
{
rez[q[i].cnt] = query(T,q[i].poz);
}
for(int i=1; i<=m; i++)
{
cout<<rez[i]<<'\n';
}
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 7 ms | 596 KB | Execution killed with signal 11 |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 7 ms | 556 KB | Execution killed with signal 11 |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 7 ms | 544 KB | Execution killed with signal 11 |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 7 ms | 596 KB | Execution killed with signal 11 |
| 2 | Halted | 0 ms | 0 KB | - |