/**
____ ____ ____ ____ ____ ____
||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], b[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 = 0, int _left = 0, int _right = 0)
{
val = _val;
left = _left;
right = _right;
}
bool operator < (const block &bk) const
{
if (val == bk.val)
return right < bk.right;
return val < bk.val;
}
};
set < block > act, blocks;
int fin[maxn], to, sz;
void shuffle_smart_init()
{
while(true)
{
block cur = *act.rbegin();
if (sz - (cur.right - cur.left + 1) + 1 > n / 2)
{
///cout << "remove " << sz << " " << cur.left << " " << cur.right << endl;
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);
blocks.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));
blocks.insert(block(a[idx], idx, gt - 1));
idx = gt;
}
}
unordered_map < int, int > rev[maxn];
block bl[maxn * 2];
int tree[8 * maxn];
int bl_cnt;
void update(int root, int left, int right, int idx)
{
if (left == right)
{
if (tree[root] == 0)
tree[root] = bl[left].right - bl[left].left + 1;
else
tree[root] = 0;
return;
}
int mid = (left + right) / 2;
if (idx <= mid)
update(root * 2, left, mid, idx);
else
update(root * 2 + 1, mid + 1, right, idx);
tree[root] = tree[root * 2] + tree[root * 2 + 1];
}
int walk(int root, int left, int right, int k)
{
if (left == right)
{
return a[bl[left].left + k - 1];
}
int mid = (left + right) / 2;
if (tree[root * 2] >= k)
return walk(root * 2, left, mid, k);
else
return walk(root * 2 + 1, mid + 1, right, k - tree[root * 2]);
}
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;
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);
update(1, 1, bl_cnt, rev[cur.left][cur.right]);
block fr = cur;
fr.right = cur.right - (sz - n / 2);
act.insert(fr);
update(1, 1, bl_cnt, rev[fr.left][fr.right]);
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));
update(1, 1, bl_cnt, rev[idx][gt - 1]);
idx = gt;
}
}
void solve()
{
cin >> n >> q;
for (int i = 1; i <= n; i ++)
{
cin >> a[i];
b[i] = 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));
blocks.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_init();
}
while(!act.empty())
{
block cur = *act.rbegin(); ///cout << to << " " << sz << " " << (cur.right - cur.left + 1) << endl;
act.erase(cur);
sz -= (cur.right - cur.left + 1);
}
for (block cur : blocks)
{
rev[cur.left][cur.right] = ++ bl_cnt;
bl[bl_cnt] = cur;
///cout << cur.val << " " << cur.left << " " << cur.right << endl;
}
for (int i = 1; i <= n; i ++)
a[i] = b[i];
shuffle_array();
i = 1;
while(i <= n)
{
act.insert(block(a[i], i, nxt_pos[i] - 1));
update(1, 1, bl_cnt, rev[i][nxt_pos[i] - 1]);
///blocks.insert(block(a[i], i, nxt_pos[i] - 1));
i = nxt_pos[i];
}
to = n;
sz = n;
for (int f = 1; f <= n; f ++)
{
for (pair < int, int > cur : ask[f])
{
ans[cur.second] = walk(1, 1, bl_cnt, cur.first);
}
shuffle_smart();
}
for (int i = 1; i <= q; i ++)
cout << ans[i] << endl;
}
int main()
{
speed();
solve();
return 0;
}
/**
10 0
3 8 2 4 9 5 10 1 6 7
*/
Compilation message
Main.cpp: In function 'void shuffle_smart_init()':
Main.cpp:117:45: warning: unused variable 'svd' [-Wunused-variable]
117 | int idx = cur.right - (sz - n / 2) + 1, svd = idx;
| ^~~
Main.cpp: In function 'void shuffle_smart()':
Main.cpp:202:45: warning: unused variable 'svd' [-Wunused-variable]
202 | int idx = cur.right - (sz - n / 2) + 1, svd = idx;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
236 ms |
41652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
661 ms |
109948 KB |
Output is correct |
| 2 |
Correct |
634 ms |
100608 KB |
Output is correct |
| 3 |
Correct |
574 ms |
94248 KB |
Output is correct |
| 4 |
Correct |
375 ms |
61560 KB |
Output is correct |
| 5 |
Correct |
429 ms |
65212 KB |
Output is correct |
| 6 |
Correct |
349 ms |
59596 KB |
Output is correct |
| 7 |
Correct |
368 ms |
56640 KB |
Output is correct |
| 8 |
Correct |
365 ms |
58268 KB |
Output is correct |
| 9 |
Correct |
384 ms |
58544 KB |
Output is correct |
| 10 |
Correct |
300 ms |
49180 KB |
Output is correct |
| 11 |
Correct |
230 ms |
44964 KB |
Output is correct |
| 12 |
Correct |
246 ms |
46380 KB |
Output is correct |
| 13 |
Correct |
285 ms |
48240 KB |
Output is correct |
| 14 |
Correct |
258 ms |
46408 KB |
Output is correct |
| 15 |
Correct |
285 ms |
48812 KB |
Output is correct |
| 16 |
Correct |
35 ms |
25164 KB |
Output is correct |
| 17 |
Correct |
498 ms |
92144 KB |
Output is correct |
| 18 |
Correct |
187 ms |
43852 KB |
Output is correct |
| 19 |
Correct |
72 ms |
28744 KB |
Output is correct |
| 20 |
Correct |
99 ms |
32980 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
206 ms |
56224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
236 ms |
41652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
