#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define pll pair<lli,lli>
#define MAX 200000
//para el vector de querys
#define p second.first
#define id second.second
lli n,q,offset,apu,a,b,t;
lli arr[MAX+2],p_arr[MAX+2]; //p_arr[i], poscion de numero i en el arreglo
vector<lli> res;
lli stree[MAX*4];
vector<pair<lli,pll> > querys;
pll sig[MAX+2];
stack<lli> pila;
void update(lli pos, lli ini, lli fin, lli l, lli r, lli val) {
if (ini > r || fin < l) return;
if (l <= ini && fin <= r) {
stree[pos] = val;
return;
}
lli mitad = (ini+fin)/2;
update(pos*2,ini,mitad,l,r,val);
update((pos*2)+1,mitad+1,fin,l,r,val);
stree[pos] = stree[pos*2] + stree[(pos*2)+1];
}
lli suma(lli pos, lli ini, lli fin, lli l, lli r) {
if (l > r) return 0;
if (ini > r || fin < l) return 0;
if (l <= ini && fin <= r) return stree[pos];
lli a;
lli mitad = (ini+fin)/2;
a = suma(pos*2,ini,mitad,l,r);
a += suma((pos*2)+1,mitad+1,fin,l,r);
return a;
}
lli busca(lli pos, lli ini, lli fin, lli sum) {
if (ini == fin) return ini;
//debugsl(pos);
//debugsl(ini);
//debugsl(fin);
//debugsl(stree[pos]);
//debug(sum);
lli mitad = (ini+fin)/2;
if (stree[pos*2] >= sum) return busca(pos*2,ini,mitad,sum);
else return busca((pos*2)+1,mitad+1,fin,sum-stree[pos*2]);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> q;
res.resize(q+2);
offset = 1;
while (offset < n) offset *= 2;
rep(i,1,n) {
cin >> arr[i];
p_arr[ arr[i] ] = i;
}
rep(i,1,q) {
cin >> a >> b;
if (a == 0) res[i] = arr[b];
else querys.push_back({a,{b,i}});
}
sort(querys.begin(), querys.end());
//pre proceso de monotone stacks
//der a izq
pila.push(n+1);
repa(i,n,1) {
while (pila.top() < arr[i]) pila.pop();
sig[arr[i]].second = pila.top();
pila.push(arr[i]);
}
// de izq a der
while (!pila.empty()) pila.pop();
pila.push(n+1);
rep(i,1,n) {
while (pila.top() < arr[i]) pila.pop();
sig[arr[i]].first = pila.top();
pila.push(arr[i]);
}
//rep(i,1,n) {
// debugsl(i);
// debugsl(sig[i].first);
// debug(sig[i].second);
//}
//correcto
//activa los nodos y haz el primer shuffle
lli mitad = (n/2);
lli dif,s,pos = 1;
p_arr[n+1] = n+1;
arr[n+1] = n+1;
while (pos <= n) {
s = p_arr[ sig[arr[pos]].second ];
if (pos <= mitad && s > mitad) s = mitad+1;
dif = s - pos;
update(1,1,offset,arr[pos],arr[pos],dif);
//debugsl(arr[pos]);
//debug(dif);
pos = s;
}
//rep(i,1,offset) {
// debugsl(i);
// debug(stree[i]);
//}
//correcto
//debug("llegue");
apu = 0;
t = 1;
while (apu < querys.size()) {
//responde querys
while (apu < querys.size() && querys[apu].first == t) {
a = busca(1,1,offset,querys[apu].p);
b = suma(1,1,offset,1,a-1);
//debugsl(querys[apu].p);
//debugsl(a);
//debug(b);
b++;
b = querys[apu].p - b;
res[querys[apu].id] = arr[ p_arr[a] + b];
apu++;
}
if (apu == querys.size()) break;
//shuffle
t++;
a = busca(1,1,offset,(n/2)+1);
b = suma(1,1,offset,1,a-1);
//debug(a);
//debug(b);
if (b == (n/2)) {
//se termino
rep(i,apu,querys.size()-1) querys[i].first = t;
continue;
}
dif = (n/2) - b;
pos = p_arr[a] + dif;
update(1,1,offset,a,a,dif);
while (arr[pos] < a) {
s = p_arr[ sig[arr[pos]].second ];
dif = s - pos;
update(1,1,offset,arr[pos],arr[pos],dif);
pos = s;
}
}
rep(i,1,q) cout << res[i] << "\n";
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:139:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
139 | while (apu < querys.size()) {
| ~~~~^~~~~~~~~~~~~~~
Main.cpp:142:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | while (apu < querys.size() && querys[apu].first == t) {
| ~~~~^~~~~~~~~~~~~~~
Main.cpp:156:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
156 | if (apu == querys.size()) break;
| ~~~~^~~~~~~~~~~~~~~~
Main.cpp:7:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
7 | #define rep(i,a,b) for(int i = (a); i <= (b); i++)
| ^
Main.cpp:168:13: note: in expansion of macro 'rep'
168 | rep(i,apu,querys.size()-1) querys[i].first = t;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
346 ms |
43128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
409 ms |
60512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
67 ms |
10412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
346 ms |
43128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
