Submission #893053

#	Time	Username	Problem	Language	Result	Execution time	Memory
893053		d4xn	Abracadabra (CEOI22_abracadabra)	C++17	10 / 100	3095 ms	25220 KiB

Main

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math,inline")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,lzcnt,mmx,abm,avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5, Q = 1e6;

int n, q, a[N], b[N], ans[Q];
tuple<int, int, int> qry[Q];

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> q;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < q; i++) {
    int x, y;
    cin >> x >> y;
    y--;
    qry[i] = make_tuple(x, y, i);
  }
  sort(qry, qry+q);

  int curr = 0;
  bool same = 0;
  for (int i = 0; i < q; i++) {
    while (!same && curr < get<0>(qry[i])) {
      curr++;

      int L = 0;
      bool bL = 1;

      int l = 0;
      int r = n/2;
      int x = 0;
      while (l < n/2 && r < n) {
        if (a[l] < a[r]) {
          b[x++] = a[l++];
          if (bL) L++;
        }
        else {
          bL = 0;
          b[x++] = a[r++];
        }
      }

      while (l < n/2) {
        b[x++] = a[l++];
      }

      bool ok = 1;
      for (int i = L; i < r; i++) {
        if (a[i] != b[i]) ok = 0;
        a[i] = b[i];
      }
      if (ok) same = 1;
    }
    ans[get<2>(qry[i])] = a[get<1>(qry[i])];
  }

  for (int i = 0; i < q; i++) {
    cout << ans[i] << "\n";
  }
}

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