Submission #1007422

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007422		aykhn	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	588 ms	41940 KiB

Main

#include <bits/stdc++.h>
 
using namespace std;

#define inf 0x3F3F3F3F

const int MXN = 2e5 + 5;

int n;
int a[MXN];
int st[MXN << 2];
int nxt[MXN], ind[MXN];

void make(int l, int r, int x, int ind, int val)
{
  if (l == r)
  {
    st[x] = val;
    return;
  }
  int mid = (l + r) >> 1;
  if (ind <= mid) make(l, mid, 2*x, ind, val);
  else make(mid + 1, r, 2*x + 1, ind, val);
  st[x] = st[2*x] + st[2*x + 1];
}
int get(int l, int r, int x, int lx, int rx)
{
  if (lx > rx) return 0;
  if (l > rx || r < lx) return 0;
  if (l >= lx && r <= rx) return st[x];
  int mid = (l + r) >> 1;
  return get(l, mid, 2*x, lx, rx) + get(mid + 1, r, 2*x + 1, lx, rx);
}
int findval(int l, int r, int x, int lx, int rx, int val)
{
  if (lx > rx) return -1;
  if (l > rx || r < lx) return -1;
  if (l >= lx && r <= rx && st[x] < val) return -1;
  if (l == r) return l;
  int mid = (l + r) >> 1;
  int A = findval(l, mid, 2*x, lx, rx, val);
  if (A == -1) return findval(mid + 1, r, 2*x + 1, lx, rx, val - st[2*x]);
  else return A;
}

int getind(int i)
{
  int x = findval(1, n, 1, 1, n, i);
  int ext = i - get(1, n, 1, 1, x - 1);
  return ind[x] + ext - 1;
}

signed main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int Q;
  cin >> n >> Q;
  for (int i = 1; i <= n; i++) 
  {
    cin >> a[i];
    ind[a[i]] = i;
  }
  vector<int> v;
  for (int i = n; i >= 1; i--)
  {
    while (!v.empty() && a[v.back()] < a[i]) v.pop_back();
    nxt[i] = (v.empty() ? n + 1 : v.back());
    v.push_back(i);
  }
  int cur = 1;
  while (cur < n + 1)
  {
    make(1, n, 1, a[cur], nxt[cur] - cur);
    cur = nxt[cur];
  }
  array<int, 3> q[Q];
  for (int i = 0; i < Q; i++)
  {
    cin >> q[i][0] >> q[i][1];
    q[i][2] = i;
  }
  sort(q, q + Q);
  int ans[Q];
  int j = 0, f = 1;
  for (array<int, 3> &i : q)
  {
    while (f && j < i[0])
    {
      int m = findval(1, n, 1, 1, n, n / 2);
      if (get(1, n, 1, 1, m) == n / 2)
      {
        f = 0;
        break;
      }
      int cur = getind(n / 2 + 1);
      int tmp = cur;
      while (cur < nxt[ind[m]])
      {
        nxt[cur] = min(nxt[cur], nxt[ind[m]]);
        make(1, n, 1, a[cur], nxt[cur] - cur);
        cur = nxt[cur];
      }
      nxt[ind[m]] = tmp;
      make(1, n, 1, m, nxt[ind[m]] - ind[m]);
      j++;
    }
    ans[i[2]] = a[getind(i[1])];
  }
  for (int i = 0; i < Q; i++) cout << ans[i] << '\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25