Submission #645632

#	Time	Username	Problem	Language	Result	Execution time	Memory
645632		Pety	Abracadabra (CEOI22_abracadabra)	C++14	100 / 100	509 ms	39612 KiB

Main

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int INF = 1e9;
const int MOD = 1e9 + 7;
const int M = 1e6+2;

int n, m, bit, p[200002], dr[200002];
pair<int, int>interval[200002];

int aib[200002];
int ans[M];

struct  queries{
  int p, t, i;
  bool operator < (const queries &other) {
    return t < other.t;
  }
} q[M];

void update (int x, int val) {
  for (int i = x; i <= n; i += (i & -i)) {
    aib[i] += val;
  }
}
int query (int x) {
  int s = 0;
  for (int i = x; i; i -= (i & -i))
     s += aib[i];
  return s;
}

int binary (int x) {
  int poz = 0;
  int s = 0;
  for (int i = (1 << bit); i; (i >>= 1)) {
    if (poz + i <= n && s + aib[poz + i] < x) {
      s += aib[poz + i];
      poz += i;
    }
  }
  return poz + 1;
}

int main () 
{
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> p[i];
  }
  for (int i = 1; i <= m; i++) {
    cin >> q[i].t >> q[i].p;
    q[i].i = i;
  }
  while ((1 << bit) <= n)
    bit++;
  bit--;
  sort(q + 1,q + m + 1);
  int ind = 1;
  while (ind <= m && q[ind].t == 0) {
    ans[q[ind].i] = p[q[ind].p];
    ind++;
  }
  stack<int>st;
  st.push(n + 1);
  p[n + 1] = n + 1;
  for (int i = n; i >= 1; i--) {
    while (p[st.top()] < p[i]) 
      st.pop();
    dr[i] = st.top();
    st.push(i);
  }
  int j = 1;
  while (j <= n) {
    if (j <= n / 2) {
      int l = j, r = min(n / 2, dr[j] - 1);
      update(p[j], r - l + 1);
      interval[p[j]] = {l, r};
      j = r + 1;
    }
    else {
      update(p[j], dr[j] - j);
      interval[p[j]] = {j, dr[j] - 1};
      j = dr[j];
    }
  }
  int time = 0;
  while (1) {
    time++;
    int val = binary(n / 2);
    int sum = query(val);
    while (ind <= m && q[ind].t == time) {
      int poz = binary(q[ind].p);
      int sum2 = query(poz - 1);
      ans[q[ind].i]  = p[interval[poz].first + q[ind].p - sum2 - 1];
      ind++;
    }
    if (sum == n / 2) 
      break;
    int overflow = sum - n / 2;
    update(val, -overflow);
    interval[val].second -= overflow;
    int j = interval[val].second + 1;
    while (j <= interval[val].second + overflow) {
      update(p[j], min(interval[val].second + overflow + 1, dr[j]) - j);
      interval[p[j]] = {j, min(interval[val].second + overflow + 1, dr[j]) - 1};
      j = min(interval[val].second + overflow + 1, dr[j]);
    } 
  }
  while (ind <= m) {
    int poz = binary(q[ind].p);
    int sum2 = query(poz - 1);
    ans[q[ind].i]  = p[interval[poz].first + q[ind].p - sum2 - 1];
    ind++;
  }
  for (int i = 1; i <= m; i++)
    cout << ans[i] << "\n";
  return 0;
}

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