/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 2e5 + 10, maxq = 1e6 + 10;
int n, q, a[maxn], ans[maxq], nxt_pos[maxn], nxt_val[maxn];
vector < pair < int, int > > ask[maxn];
void shuffle_array()
{
deque < int > d1, d2;
for (int i = 1; i <= n / 2; i ++)
d1.push_back(a[i]);
for (int i = n / 2 + 1; i <= n; i ++)
d2.push_back(a[i]);
deque < int > res;
while(!d1.empty() && !d2.empty())
{
if (d1.front() < d2.front())
{
res.push_back(d1.front());
d1.pop_front();
}
else
{
res.push_back(d2.front());
d2.pop_front();
}
}
while(!d1.empty())
{
res.push_back(d1.front());
d1.pop_front();
}
while(!d2.empty())
{
res.push_back(d2.front());
d2.pop_front();
}
for (int i = 1; i <= n; i ++)
a[i] = res[i - 1];
}
struct block
{
int val, left, right;
block(int _val, int _left, int _right)
{
val = _val;
left = _left;
right = _right;
}
bool operator < (const block &bk) const
{
return val < bk.val;
}
};
set < block > act;
int fin[maxn], to, sz;
void shuffle_smart()
{
while(true)
{
block cur = *act.rbegin();
if (sz - (cur.right - cur.left + 1) + 1 > n / 2)
{
///cout << sz << " " << cur.left << " " << cur.right << endl;
for (int i = cur.right; i >= cur.left; i --)
fin[to --] = a[i];
act.erase(cur);
sz -= (cur.right - cur.left + 1);
}
else
{
break;
}
}
if (sz == n / 2)
return;
block cur = *act.rbegin();
act.erase(cur);
block fr = cur;
fr.right = cur.right - (sz - n / 2);
act.insert(fr);
int idx = cur.right - (sz - n / 2) + 1;
while(idx <= cur.right)
{
int gt = nxt_pos[idx];
act.insert(block(a[idx], idx, gt - 1));
idx = gt;
}
/**cout << "------------" << endl;
for (block cur : act)
{
cout << "here " << cur.val << " " << cur.left << " " << cur.right << endl;
}*/
}
void solve()
{
cin >> n >> q;
for (int i = 1; i <= n; i ++)
{
cin >> a[i];
}
int tp = 0;
for (int i = 1; i <= q; i ++)
{
int t, v;
cin >> t >> v;
t = min(t, n);
tp = t;
if (t == 0)
ans[i] = a[v];
else
ask[t].push_back({v, i});
}
shuffle_array();
/**for (int i = 1; i <= n; i ++)
cout << a[i] << " ";
cout << endl;*/
stack < int > st;
for (int i = 1; i <= n; i ++)
{
while(!st.empty() && a[st.top()] < a[i])
{
nxt_pos[st.top()] = i;
st.pop();
}
st.push(i);
}
while(!st.empty())
{
nxt_pos[st.top()] = n + 1;
st.pop();
}
int i = 1;
while(i <= n)
{
act.insert(block(a[i], i, nxt_pos[i] - 1));
i = nxt_pos[i];
}
to = n;
sz = n;
for (int f = 1; f < tp; f ++)
{
shuffle_smart();
}
while(!act.empty())
{
block cur = *act.rbegin();
for (int i = cur.right; i >= cur.left; i --)
fin[to --] = a[i];
act.erase(cur);
sz -= (cur.right - cur.left + 1);
}
for (pair < int, int > cur : ask[tp])
ans[cur.second] = fin[cur.first];
for (int i = 1; i <= q; i ++)
cout << ans[i] << endl;
}
int main()
{
speed();
///freopen("test.txt", "r", stdin);
///freopen("output.txt", "w", stdout);
solve();
return 0;
}
/**
10 0
3 8 2 4 9 5 10 1 6 7
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
189 ms |
20636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
230 ms |
37740 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
50 ms |
17912 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
189 ms |
20636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
