#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
// #define int long long
typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
template<typename T, typename U>
ostream & operator << (ostream &out, const pair<T, U> &c) {
out << c.first << ' ' << c.second;
return out;
}
template<typename T>
ostream & operator << (ostream &out, vector<T> &v) {
const int sz = v.size();
for (int i = 0; i < sz; i++) {
if (i) out << ' ';
out << v[i];
}
return out;
}
template<typename T>
istream & operator >> (istream &in, vector<T> &v) {
for (T &x : v) in >> x;
return in;
}
template<typename T>
void mxx(T &a, T b){if(b > a) a = b;}
template<typename T>
void mnn(T &a, T b){if(b < a) a = b;}
const int mxn = 2e5 + 10, mxq = 1e6 + 10;
vector<pair<int, int>> qu[mxn];
int a[mxn], ans[mxq], nxt[mxn], did[mxn];
signed main() {
fast;
int n, q;
cin >> n >> q;
for(int i = 1; i <= n; i++) {
cin >> a[i];
did[i] = -1;
}
for(int i = 1; i <= q; i++) {
int t, id;
cin >> t >> id;
mnn(t, n);
if(t == 0) {
ans[i] = a[id];
} else {
qu[t].eb(id, i);
}
}
stack<pair<int, int>> st;
for(int i = n; i >= 1; i--) {
while(st.size() && st.top().ff < a[i]) st.pop();
if(st.size()) nxt[i] = st.top().ss;
else nxt[i] = n + 1;
st.emplace(a[i], i);
}
set<pair<int, pair<int, int>>> s;
for(int i = 1; i <= n; i = nxt[i]) {
s.emplace(a[i], make_pair(i, nxt[i] - 1));
assert(i <= nxt[i] - 1);
}
int len = n;
for(int t = 1; t <= n; t++) {
while(1) {
auto val = *s.rbegin();
if(len - (val.ss.ss - val.ss.ff + 1) >= n / 2) {
len -= (val.ss.ss - val.ss.ff + 1);
for(int i = val.ss.ff; i <= val.ss.ss; i++) {
did[len + (i - val.ss.ff + 1)] = a[i];
}
s.erase(s.find(val));
} else {
break;
}
}
if(len > n / 2) {
auto val = *s.rbegin();
s.erase(s.find(val));
len -= (val.ss.ss - val.ss.ff + 1);
assert(len < n / 2);
s.emplace(val.ff, make_pair(val.ss.ff, val.ss.ff + n / 2 - len - 1));
assert(val.ss.ff <= val.ss.ff + n / 2 - len - 1);
for(int i = val.ss.ff + n / 2 - len; i <= val.ss.ss; i = nxt[i]) {
s.emplace(a[i], make_pair(i, nxt[i] - 1));
assert(i <= nxt[i] - 1);
}
len += (val.ss.ss - val.ss.ff + 1);
}
sort(all(qu[t]));
auto it = s.begin();
int lol = 0;
for(auto U : qu[t]) {
int id = U.ff;
int i = U.ss;
if(id > len) {
ans[i] = did[id];
continue;
}
while(it != s.end() && lol + (*it).ss.ss - (*it).ss.ff + 1 < id) {
lol += (*it).ss.ss - (*it).ss.ff + 1;
it++;
}
ans[i] = a[(*it).ss.ff + id - lol - 1];
}
}
for(int i = 1; i <= q; i++) {
cout << ans[i] << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
219 ms |
22712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
281 ms |
30572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
77 ms |
12328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
219 ms |
22712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
