/**
____ ____ ____ ____ ____ ____
||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 << "remove " << 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;
/** for (block cur : act)
{
cout << "here " << cur.val << " " << cur.left << " " << cur.right << endl;
}*/
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, svd = idx;
int sum_size = 0;
//cout << idx << " : " << cur.right << endl;
while(idx <= cur.right)
{
int gt = nxt_pos[idx];
gt = min(gt, cur.right + 1);
sum_size += (gt - idx);
act.insert(block(a[idx], idx, gt - 1));
///cout << idx << " -- " << gt << " " << sum_size << endl;
idx = gt;
}
/**if (sum_size != (sz - n / 2))
{
cout << "wtf " << (sz - n / 2) << " "<< sum_size << endl;
for (block cur : act)
{
cout << "here " << cur.val << " " << cur.left << " " << cur.right << " " << svd << endl;
}
}*/
// cout << "------------" << 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(); ///cout << to << " " << sz << " " << (cur.right - cur.left + 1) << endl;
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
*/
Compilation message
Main.cpp: In function 'void shuffle_smart()':
Main.cpp:114:45: warning: unused variable 'svd' [-Wunused-variable]
114 | int idx = cur.right - (sz - n / 2) + 1, svd = idx;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
455 ms |
20692 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
697 ms |
29072 KB |
Output is correct |
| 2 |
Correct |
710 ms |
48368 KB |
Output is correct |
| 3 |
Correct |
604 ms |
38320 KB |
Output is correct |
| 4 |
Correct |
541 ms |
34500 KB |
Output is correct |
| 5 |
Correct |
561 ms |
36236 KB |
Output is correct |
| 6 |
Correct |
517 ms |
33312 KB |
Output is correct |
| 7 |
Correct |
648 ms |
40484 KB |
Output is correct |
| 8 |
Correct |
625 ms |
39316 KB |
Output is correct |
| 9 |
Correct |
536 ms |
35328 KB |
Output is correct |
| 10 |
Correct |
585 ms |
37144 KB |
Output is correct |
| 11 |
Correct |
481 ms |
31800 KB |
Output is correct |
| 12 |
Correct |
481 ms |
31848 KB |
Output is correct |
| 13 |
Correct |
564 ms |
36452 KB |
Output is correct |
| 14 |
Correct |
494 ms |
32696 KB |
Output is correct |
| 15 |
Correct |
625 ms |
38088 KB |
Output is correct |
| 16 |
Correct |
63 ms |
9348 KB |
Output is correct |
| 17 |
Correct |
572 ms |
38280 KB |
Output is correct |
| 18 |
Correct |
422 ms |
29924 KB |
Output is correct |
| 19 |
Correct |
152 ms |
12956 KB |
Output is correct |
| 20 |
Correct |
196 ms |
16036 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
111 ms |
9264 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
455 ms |
20692 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
