#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e16+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e16+7;
const int tree_siz = 1024*512-1;
struct seg_tree
{
pll drzewo[tree_siz+1];
ll oper[tree_siz+1];
seg_tree()
{
rep2(i,tree_siz/2+1,tree_siz)
{
drzewo[i].ss = i - (tree_siz/2+1);
drzewo[i].ff = -1e16;
}
for(int i = tree_siz/2; i >= 1; i--)
{
drzewo[i] = max(drzewo[i*2],drzewo[i*2+1]);
}
}
void spych(int v)
{
drzewo[v*2+1].ff += oper[v];
drzewo[v*2].ff += oper[v];
oper[v*2+1] += oper[v];
oper[v*2] += oper[v];
oper[v] = 0;
}
void add_seg(int akt, int p1, int p2, int s1, int s2, ll w)
{
if(p2 < s1 || p1 > s2) return;
if(p1 >= s1 && p2 <= s2)
{
drzewo[akt].ff += w;
oper[akt] += w;
return;
}
spych(akt);
add_seg(akt*2,p1,(p1+p2)/2,s1,s2,w);
add_seg(akt*2+1,(p1+p2)/2+1,p2,s1,s2,w);
drzewo[akt] = max(drzewo[akt*2],drzewo[akt*2+1]);
}
pll get_max(int akt, int p1, int p2, int s1, int s2)
{
if(p2 < s1 || p1 > s2) return {-1e16,-1};
if(p1 >= s1 && p2 <= s2)
{
return drzewo[akt];
}
spych(akt);
return max(get_max(akt*2,p1,(p1+p2)/2,s1,s2),get_max(akt*2+1,(p1+p2)/2+1,p2,s1,s2));
}
void set_val(int akt, int p1, int p2, int poz, ll val)
{
if(p1 == p2)
{
drzewo[akt].ff = val;
return;
}
spych(akt);
if((p1+p2)/2 >= poz) set_val(akt*2,p1,(p1+p2)/2,poz,val);
else set_val(akt*2+1,(p1+p2)/2+1,p2,poz,val);
drzewo[akt] = max(drzewo[akt*2],drzewo[akt*2+1]);
}
pll find_nxt(int akt, int p1, int p2, ll val)
{
if(p1 == p2)
{
if(drzewo[akt].ff <= val)
{
return drzewo[akt];
}
return {-1,-1};
}
spych(akt);
if(drzewo[akt*2].ff <= val) return max(drzewo[akt*2],find_nxt(akt*2+1,(p1+p2)/2+1,p2,val));
return find_nxt(akt*2,p1,(p1+p2)/2,val);
}
pll last_on_rek(int akt, int p1, int p2)
{
if(p1 == p2)
{
return {p1,drzewo[akt].ff};
}
spych(akt);
if(drzewo[akt*2+1].ff >= 0) return last_on_rek(akt*2+1,(p1+p2)/2+1,p2);
return last_on_rek(akt*2,p1,(p1+p2)/2);
}
pll get_last_on(int akt, int p1, int p2, int s1, int s2)
{
if(p2 < s1 || p1 > s2) return {-1e16,-1};
if(p1 >= s1 && p2 <= s2)
{
if(drzewo[akt].ff >= 0) return last_on_rek(akt,p1,p2);
return {-1e16,-1};
}
spych(akt);
pll w1 = get_last_on(akt*2+1,(p1+p2)/2+1,p2,s1,s2);
if(w1.ss != -1) return w1;
return get_last_on(akt*2,p1,(p1+p2)/2,s1,s2);
}
};
struct query
{
int time,pos,ind;
bool operator<(const query& other) const
{
return time < other.time;
}
};
int init_pos[200'001];
int arr[200'001];
int nxt_big[200'001];
int seg_siz[200'001];
bool is_seg[200'001];
int query_ans[1'000'001];
seg_tree L_tree,R_tree;
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//random();
int n,q;
cin >> n >> q;
rep(i,n)
{
cin >> arr[i];
init_pos[arr[i]] = i;
}
vector<query> que;
rep(qq,q)
{
int t,i;
cin >> t >> i;
i--;
que.pb({t,i,qq});
}
sort(all(que));
stack<int> st;
for(int i = n-1; i >= n/2; i--)
{
while(!st.empty() && arr[st.top()] < arr[i])
{
st.pop();
}
if(siz(st) != 0)
{
nxt_big[arr[i]] = arr[st.top()];
}
else
{
nxt_big[arr[i]] = -1;
}
st.push(i);
}
st = {};
for(int i = n/2-1; i >= 0; i--)
{
while(!st.empty() && arr[st.top()] < arr[i])
{
st.pop();
}
if(siz(st) != 0)
{
nxt_big[arr[i]] = arr[st.top()];
}
else
{
nxt_big[arr[i]] = -1;
}
st.push(i);
}
//L
int cur = arr[0];
while(cur != -1)
{
int nxt = nxt_big[cur];
L_tree.set_val(1,0,tree_siz/2,cur,init_pos[cur]);
is_seg[cur] = 1;
if(nxt == -1)
{
seg_siz[cur] = n/2 - init_pos[cur];
}
else
{
seg_siz[cur] = init_pos[nxt] - init_pos[cur];
}
cur = nxt;
}
cur = arr[n/2];
while(cur != -1)
{
int nxt = nxt_big[cur];
R_tree.set_val(1,0,tree_siz/2,cur,init_pos[cur]);
is_seg[cur] = 1;
if(nxt == -1)
{
seg_siz[cur] = n - init_pos[cur];
}
else
{
seg_siz[cur] = init_pos[nxt] - init_pos[cur];
}
cur = nxt;
}
int cur_q = 0;
int ok_suf = n+1;
rep(i,n+2)
{
// rep2(i,1,n)
// {
// cerr << L_tree.get_max(1,0,tree_siz/2,i,i).ff << " " << R_tree.get_max(1,0,tree_siz/2,i,i).ff << " " << i << " " << seg_siz[i] << " pos\n";
// }
// cerr << "\n\n";
while(cur_q != siz(que) && que[cur_q].time == i)
{
pii nxt;
if(que[cur_q].pos < n/2)
{
nxt = L_tree.find_nxt(1,0,tree_siz/2,que[cur_q].pos);
}
else
{
nxt = R_tree.find_nxt(1,0,tree_siz/2,que[cur_q].pos);
}
query_ans[que[cur_q].ind] = arr[init_pos[nxt.ss] + que[cur_q].pos - nxt.ff];
cur_q++;
}
while(true)
{
if(ok_suf == 0) break;
pii seg = R_tree.get_max(1,0,tree_siz/2,0,ok_suf-1);
if(seg.ff < 0) break;
R_tree.set_val(1,0,tree_siz/2,seg.ss,-1e16);
pii prev = L_tree.get_last_on(1,0,tree_siz/2,0,seg.ss);
if(prev.ss != -1)
{
int new_pos = prev.ss + seg_siz[prev.ff];
L_tree.set_val(1,0,tree_siz/2,seg.ss,new_pos);
L_tree.add_seg(1,0,tree_siz/2,seg.ss+1,n+1,seg_siz[seg.ss]);
}
else
{
int new_pos = 0;
L_tree.set_val(1,0,tree_siz/2,seg.ss,new_pos);
L_tree.add_seg(1,0,tree_siz/2,seg.ss+1,n+1,seg_siz[seg.ss]);
}
}
while(true)
{
pii seg = L_tree.get_max(1,0,tree_siz/2,0,tree_siz/2);
if(seg.ff >= n/2)
{
ok_suf = min(ok_suf,seg.ss);
L_tree.set_val(1,0,tree_siz/2,seg.ss,-1e16);
R_tree.set_val(1,0,tree_siz/2,seg.ss,seg.ff);
continue;
}
if(seg.ff+seg_siz[seg.ss] == n/2) break;
int end_poz = init_pos[seg.ss] + seg_siz[seg.ss];
int cur = arr[init_pos[seg.ss] + n/2 - seg.ff];
seg_siz[seg.ss] = n/2 - seg.ff;
int cur_pos = n/2;
while(cur != -1 && is_seg[cur] == 0)
{
int nxt = nxt_big[cur];
R_tree.set_val(1,0,tree_siz/2,cur,cur_pos);
is_seg[cur] = 1;
if(nxt == -1)
{
seg_siz[cur] = end_poz - init_pos[cur];
}
else
{
seg_siz[cur] = min(end_poz - init_pos[cur],init_pos[nxt] - init_pos[cur]);
cur_pos += init_pos[nxt] - init_pos[cur];
}
cur = nxt;
}
break;
}
}
while(cur_q != siz(que))
{
pii nxt;
if(que[cur_q].pos < n/2)
{
nxt = L_tree.find_nxt(1,0,tree_siz/2,que[cur_q].pos);
}
else
{
nxt = R_tree.find_nxt(1,0,tree_siz/2,que[cur_q].pos);
}
query_ans[que[cur_q].ind] = arr[init_pos[nxt.ss] + que[cur_q].pos - nxt.ff];
cur_q++;
}
rep(i,q)
{
cout << query_ans[i] << "\n";
}
}
Compilation message (stderr)
Main.cpp:26:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.000000000000005e+16' to '2147483647' [-Woverflow]
26 | const int INF = 1e16+50;
| ~~~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |