/***********************************************
* auth: tapilyoca *
* date: 07/07/2025 at 22:42:20 *
* dots: https://github.com/tapilyoca/dotilyoca *
***********************************************/
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9+7;
template<typename T>
using vec = vector<T>;
// using ll = long long;
using ll = int;
using vll = vec<ll>;
using vvll = vec<vll>;
using pll = pair<ll,ll>;
using str = string;
#define pb push_back
#define dbg(x) if(1) cerr << #x << ": " << x << endl;
/***********************************************/
struct Segment {
ll front, sstart, send, size;
Segment() : sstart(0), send(0), front(0), size(0) {}
Segment(ll s, ll e, ll f) {
sstart = s;
send = e;
front = f;
size = e-s+1;
}
bool operator>(const Segment&two) const {
if(front == two.front) {
if(sstart == two.sstart) {
return send > two.send;
}
return sstart > two.sstart;
}
return front > two.front;
}
bool operator<(const Segment&two) const {
if(front == two.front) {
if(sstart == two.sstart) {
return send < two.send;
}
return sstart<two.sstart;
}
return front < two.front;
}
bool operator==(const Segment&two) const {
return front == two.front and sstart==two.sstart and send==two.send and size==two.size;
}
void print() {
cerr << front << ": (" << sstart << ", " << send << ") ";
}
};
struct Segtree {
ll l, r;
Segtree *lt, *rt;
Segment val;
ll sum;
inline void combine() {
sum = lt->sum + rt->sum;
}
Segtree(ll left, ll right, vec<Segment>&a) {
sum = 0ll;
l = left;
r = right;
lt = rt = nullptr;
if(l == r) {
val = a[l];
return;
}
ll m = (l+r)>>1;
lt = new Segtree(l,m,a);
rt = new Segtree(m+1,r,a);
}
inline void activate(ll i, ll b) {
if(i < l or r < i) return;
if(i == l and l == r) {
sum += val.size * b;
return;
}
lt->activate(i,b);
rt->activate(i,b);
combine();
}
inline ll query_sum(ll ql, ll qr) {
if(qr < l or r < ql) return 0;
if(ql <= l and r <= qr) return sum;
return lt->query_sum(ql,qr) + rt->query_sum(ql,qr);
}
};
inline ll walk(ll x, Segtree* root, Segtree* st) {
if(st->l == st->r) {
// cerr << "Found it for " << x << " on segment ";
// st->val.print();
// cerr << endl;
ll lt_cover = (st->l == 0 ? 0 : root->query_sum(0,st->l - 1));
ll leftover = x - lt_cover;
ll og_index = leftover + st->val.sstart;
// cerr << "Left covers the first " << lt_cover << endl;
return og_index;
}
ll lt_cover = root->query_sum(0,st->lt->r);
if(lt_cover > x) {
return walk(x, root, st->lt);
} else {
return walk(x, root, st->rt);
}
}
struct Query {
ll t, x;
Query() : t(0), x(0) {}
Query(ll tt, ll xx) {
t = tt;
x = xx;
}
bool operator>(const Query&two) const {
return t > two.t;
}
bool operator<(const Query&two) const {
return t < two.t;
}
};
inline vll riffle(vll &at) {
vll a, b;
ll n = at.size();
for(int i = 0; i < n/2; i++) {
a.pb(at[i]);
}
for(int j = n/2; j < n; j++) {
b.pb(at[j]);
}
vll out;
ll lp = 0, rp = 0;
while(lp != n/2 and rp != n/2) {
if(a[lp] < b[rp]) {
out.pb(a[lp]);
lp++;
} else {
out.pb(b[rp]);
rp++;
}
}
for(int i = lp; i < n/2; i++) out.pb(a[i]);
for(int i = rp; i < n/2; i++) out.pb(b[i]);
return out;
}
inline vll segmentize(vll &a) {
ll n = a.size();
stack<pll> st;
vll out(n,1e18);
for(int i = n-1; i >= 0; i--) {
while(!st.empty() and st.top().first < a[i]) st.pop();
if(!st.empty()) out[i] = st.top().second;
// cerr << i << " " << out[i] << endl;
st.push({a[i],i});
}
return out;
}
void solve() {
ll n, q;
cin >> n >> q;
vll state(n,0);
for(int i = 0; i < n; i++) {
cin >> state[i];
}
ll T = -1;
vec<pair<Query,ll>> queries(q);
vll ans(q,0);
for(int i = 0; i < q; i++) {
ll a, b;
cin >> a >> b;
b--;
queries[i] = {Query(a,b),i};
T = max(T,a);
} sort(queries.begin(),queries.end());
T += 2;
vll stateTwo = riffle(state);
vll next_seg = segmentize(stateTwo);
// for(auto [qx,i] : queries) {
// cerr << qx.t << " " << qx.x << " " << i << endl;
// }
ll query_pointer = 0;
while(query_pointer < q and queries[query_pointer].first.t < 2) {
if(queries[query_pointer].first.t == 0) {
ans[queries[query_pointer].second] = state[queries[query_pointer].first.x];
} else {
ans[queries[query_pointer].second] = stateTwo[queries[query_pointer].first.x];
}
query_pointer++;
}
set<Segment> curr_state;
set<Segment> all_states_evers;
for(ll at = 0; at != 1e18; at = next_seg[at]) {
ll one = at;
ll two = (next_seg[at] == 1e18 ? n-1 : next_seg[at] - 1);
curr_state.insert(Segment(one,two,stateTwo[at]));
all_states_evers.insert(Segment(one,two,stateTwo[at]));
}
ll state_size = n;
for(int shuffles = 1; shuffles <= T; shuffles++) {
// dbg(shuffles);
while(state_size > n/2) {
if(state_size - (*prev(curr_state.end())).size < n/2) break;
all_states_evers.insert(*prev(curr_state.end()));
state_size -= (*prev(curr_state.end())).size;
curr_state.erase(prev(curr_state.end()));
// cerr << "hee hee hee haw" << endl;
}
if(state_size == n/2) break;
// get the middle seg
Segment midSeg = *curr_state.rbegin();
curr_state.erase(prev(curr_state.end()));
ll newSS = state_size - midSeg.size;
curr_state.insert(Segment(midSeg.sstart, midSeg.sstart + (n/2 - newSS) - 1, midSeg.front));
all_states_evers.insert(Segment(midSeg.sstart, midSeg.sstart + (n/2 - newSS) - 1, midSeg.front));
// resegment it
for(ll at = midSeg.sstart + (n/2 - newSS); at <= midSeg.send; at = next_seg[at]) {
ll one = at;
ll two = (next_seg[at] > midSeg.send ? midSeg.send : next_seg[at] - 1);
curr_state.insert(Segment(one,two,stateTwo[at]));
all_states_evers.insert(Segment(one,two,stateTwo[at]));
}
}
while(!curr_state.empty()) {
all_states_evers.insert(*prev(curr_state.end()));
curr_state.erase(prev(curr_state.end()));
}
vec<Segment> all_states_ever(all_states_evers.begin(), all_states_evers.end());
map<Segment,ll> seg_to_index;
for(int i = 0; i < all_states_ever.size(); i++) {
seg_to_index[all_states_ever[i]] = i;
}
Segtree st(0,all_states_ever.size()-1,all_states_ever);
// cerr << "Segtree created." << endl;
for(ll at = 0; at != 1e18; at = next_seg[at]) {
ll one = at;
ll two = (next_seg[at] == 1e18 ? n-1 : next_seg[at] - 1);
curr_state.insert({one,two,stateTwo[at]});
st.activate(seg_to_index[{one,two,stateTwo[at]}],1);
// cerr << "Activated: " << stateTwo[at] << ": " << one << " " << two << endl;
}
// cerr << "Initialized" << endl;
state_size = n;
for(int shuffles = 1; shuffles <= T; shuffles++) {
if(query_pointer == q) break;
while(state_size > n/2) {
if(state_size - (*prev(curr_state.end())).size < n/2) break;
state_size -= (*prev(curr_state.end())).size;
curr_state.erase(prev(curr_state.end()));
}
if(state_size == n/2) break;
// get the middle seg
Segment midSeg = *curr_state.rbegin();
st.activate(seg_to_index[*prev(curr_state.end())],-1);
curr_state.erase(prev(curr_state.end()));
ll newSS = state_size - midSeg.size;
curr_state.insert({midSeg.sstart, midSeg.sstart + (n/2 - newSS) - 1, midSeg.front});
st.activate(seg_to_index[{midSeg.sstart, midSeg.sstart + (n/2 - newSS) - 1, midSeg.front}],1);
// resegment it
for(ll at = midSeg.sstart + (n/2 - newSS); at <= midSeg.send; at = next_seg[at]) {
ll one = at;
ll two = (next_seg[at] > midSeg.send ? midSeg.send : next_seg[at] - 1);
curr_state.insert({one,two,stateTwo[at]});
st.activate(seg_to_index[{one,two,stateTwo[at]}],1);
}
while(query_pointer < q and shuffles + 1 == queries[query_pointer].first.t) {
ll ogdex = walk(queries[query_pointer].first.x, &st, &st);
ans[queries[query_pointer].second] = stateTwo[ogdex];
query_pointer++;
}
}
while(query_pointer < q) {
ll ogdex = walk(queries[query_pointer].first.x, &st, &st);
// dbg(ogdex)
ans[queries[query_pointer].second] = stateTwo[ogdex];
query_pointer++;
}
for(int i = 0; i < q; i++) {
cout << ans[i] << endl;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
while(t--) {
solve();
}
return 0;
}
/*
7 5 2 8 4 3 6 1 9 10
3 6 1 7 5 2 8 4 9 10
2 3 6 1 7 5 8 4 9 10
[2] [3] [5] [6 1] [7] [8 4] [9] [10]
2 1 4 5 6 3
*/
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In function 'vll segmentize(vll&)':
Main.cpp:186:15: warning: overflow in conversion from 'double' to 'std::vector<int>::value_type' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
186 | vll out(n,1e18);
| ^~~~
# | 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... |