#include<bits/stdc++.h>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("trapv")
#define st first
#define nd second
#define pb push_back
#define pp pop_back
#define eb emplace_back
#define mp(a, b) make_pair(a, b)
#define all(x) (x).begin(), (x).end()
#define rev(x) reverse(all(x))
#define sor(x) sort(all(x))
#define sz(x) (int)(x).size()
#define rsz(x) resize(x)
using namespace std;
///~~~~~~~~~~~~~~~~~~~~~~~~~~
template <typename H, typename T>
ostream& operator<<(ostream& os, pair<H, T> m){
return os <<"("<< m.st<<", "<<m.nd<<")";
}
template <typename H>
ostream& operator<<(ostream& os, vector<H> V){
os<<"{";
for(int i=0; i<V.size(); i++){
if(i)os<<" ";
os<<V[i];
}
os<<"}";
return os;
}
void debug(){cerr<<"\n";}
template <typename H, typename... T>
void debug(H h, T... t) {cerr<<h; if (sizeof...(t)) cerr << ", "; debug(t...);}
#define deb(x...) cerr<<#x<<" = ";debug(x);
///~~~~~~~~~~~~~~~~~~~~~~~~~
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii > vii;
typedef vector<ll> vl;
typedef vector<pll> vll;
typedef string str;
#define BOOST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int N=(1<<18), INF=1e9+5, mod=1e9+7;
int val[N], ile[N+N], par[N], siz[N], gdzie[N];
vi co[N], sum[N];
void add(int i, int v){
for(i+=N; i; i>>=1){
ile[i]+=v;
}
}
pair<int, int> find(int s){
int v=1;
while(v<N){
if(ile[v+v]<s){
s-=ile[v+v];
v=v+v+1;
}
else v=v+v;
}
return mp(v-N, s);
}
/*void split(int i, int a){
assert(a!=siz[i]);
//deb(i, siz[i], a);
add(val[i], a-siz[i]);
while(siz[i]>a){
int j=co[i].back();
co[i].pp();
siz[i]-=siz[j];
add(val[j], siz[j]);
if(siz[i]<a){
split(j, a-siz[i]);
siz[i]+=siz[j];
co[i].pb(j);
add(val[j], -siz[j]);
}
}
//add(val[i], siz[i]);
}*/
int ans[int(1e6+5)];
set<int> S;
int roz(int i){
return (*S.upper_bound(i))-i;
}
void split(int i, int s){
add(val[i], s-roz(i));
int t=i+s-1;
//deb(i, s, t);
int tt=t;
vector<int> V;
while(t!=i){
if(t==co[par[t]].back()){
break;
}
//deb("a");
V.pb(t);
t=par[t];
}
rev(V);
while(V.size()){
t=V.back();
while(co[par[t]].back()!=t){
//deb(co[t].back());
add(val[co[par[t]].back()], roz(co[par[t]].back()));
S.insert(co[par[t]].back());
co[par[t]].pp();
}
V.pp();
}
t=tt;
while(co[t].back()!=t){
add(val[co[t].back()], roz(co[t].back()));
S.insert(co[t].back());
co[t].pp();
}
}
int main(){
BOOST;
int n, q;
cin>>n>>q;
vi V;
val[0]=n+5;
V.pb(0);
S.insert(n+1);
for(int i=1; i<=n; i++){
cin>>val[i];
gdzie[val[i]]=i;
while(val[V.back()]<val[i])V.pp();
par[i]=V.back();
V.pb(i);
}
for(int i=n; i>0; i--){
siz[i]++;
siz[par[i]]+=siz[i];
co[i].pb(i);
//sum[i].pb(1);
}
for(int i=1; i<=n; i++){
co[par[i]].pb(i);
//sum[par[i]].pb(sum[par[i]].back()+siz[i]);
if(par[i]==0){
add(val[i], siz[i]);
S.insert(i);
}
}
//deb(co[6]);
vector<pair<pii, int> > Q(q);
for(int qq=0; qq<q; qq++){
cin>>Q[qq].st.st>>Q[qq].st.nd;
Q[qq].nd=qq;
}
sor(Q);
int wsk=0;
for(int t=0; ;t++){
assert(ile[1]==n);
bool b=1;
while(wsk<q && Q[wsk].st.st==t){
pii a=find(Q[wsk].st.nd);
//deb(a, Q[wsk]);
ans[Q[wsk].nd]=val[gdzie[a.st]+a.nd-1];
wsk++;
}
b=0;
pii c=find(n/2);
if(c.nd!=roz(gdzie[c.st]))split(gdzie[c.st], c.nd), b=1;
//for(int i=1; i<=n; i++)cerr<<ile[N+i]<<" ";cerr<<"\n";
if(!b){
while(wsk<q){
pii a=find(Q[wsk].st.nd);
deb(a, wsk);
ans[Q[wsk].nd]=val[gdzie[a.st]+a.nd-1];
wsk++;
}
break;
}
}
for(int i=0; i<q; i++)cout<<ans[i]<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
512 ms |
32916 KB |
Output is correct |
| 2 |
Correct |
485 ms |
32952 KB |
Output is correct |
| 3 |
Correct |
490 ms |
32144 KB |
Output is correct |
| 4 |
Runtime error |
313 ms |
56220 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
504 ms |
56012 KB |
Output is correct |
| 2 |
Correct |
442 ms |
56120 KB |
Output is correct |
| 3 |
Correct |
442 ms |
50624 KB |
Output is correct |
| 4 |
Runtime error |
274 ms |
64372 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
149 ms |
25544 KB |
Output is correct |
| 2 |
Correct |
119 ms |
25636 KB |
Output is correct |
| 3 |
Correct |
123 ms |
25328 KB |
Output is correct |
| 4 |
Runtime error |
68 ms |
38404 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
512 ms |
32916 KB |
Output is correct |
| 2 |
Correct |
485 ms |
32952 KB |
Output is correct |
| 3 |
Correct |
490 ms |
32144 KB |
Output is correct |
| 4 |
Runtime error |
313 ms |
56220 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
