Submission #985813

#	Time	Username	Problem	Language	Result	Execution time	Memory
985813		asdfgrace	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	630 ms	40636 KiB

Main

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

#define dbg(x) //x
#define prt(x) dbg(cerr << x)
#define pv(x) dbg(cerr << #x << " = " << x << '\n')
#define pv2(x) dbg(cerr << #x << " = " << x.first << ',' << x.second << '\n')
#define parr(x) dbg(prt(#x << " = { "); for (auto y : x) prt(y << ' '); prt("}\n");)
#define parr2(x) dbg(prt(#x << " = { "); for (auto [y, z] : x) prt(y << ',' << z << "  "); prt("}\n");)
#define parr2d(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr(arr);} prt('\n'));
#define parr2d2(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr2(arr);} prt('\n'));

struct FenwickTree {
  int n;
  vector<int> tree;
  
  FenwickTree(int x) {
    n = x;
    tree.resize(n + 1, 0);
  }
  
  void add(int k, int x) {
    for (int i = k + 1; i <= n; i += (i & (-i))) {
      tree[i] += x;
    }
  }
  
  int pref(int r) {
    int sum = 0;
    for (int i = r; i > 0; i -= (i & (-i))) {
      sum += tree[i];
    }
    return sum;
  }
  
  int quer(int l, int r) {
    return pref(r + 1) - pref(l);
  }
};

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int n, q;
  cin >> n >> q;
  vector<int> a(n), at(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    a[i]--;
    at[a[i]] = i;
  }
  vector<int> nl(n);
  stack<int> sta;
  for (int i = n - 1; i >= 0; i--) {
    while (!sta.empty() && a[sta.top()] < a[i]) {
      sta.pop();
    }
    if (sta.empty()) {
      nl[i] = n;
    } else {
      nl[i] = sta.top();
    }
    sta.push(i);
  }
  vector<array<int, 3>> quer(q);
  for (int i = 0; i < q; i++) {
    cin >> quer[i][0] >> quer[i][1];
    quer[i][1]--;
    quer[i][2] = i;
  }
  sort(quer.begin(), quer.end());
  vector<int> ans(q);
  vector<int> sz(n, 0);
  int pmx = -1;
  for (int i = 0; i < n / 2; i++) {
    if (a[i] > pmx) {
      pmx = a[i];
    }
    sz[pmx]++;
  }
  pmx = -1;
  for (int i = n / 2; i < n; i++) {
    if (a[i] > pmx) {
      pmx = a[i];
    }
    sz[pmx]++;
  }
  FenwickTree fenw(n);
  for (int i = 0; i < n; i++) {
    fenw.add(i, sz[i]);
  }
  int ptr = 0; bool done = false;
  while (ptr < q && quer[ptr][0] == 0) {
    ans[quer[ptr][2]] = a[quer[ptr][1]];
    ptr++;
  }
  for (int it = 1; ptr < q; it++) {
    int l = 0, r = n - 1;
    while (r > l) {
      int m = (l + r) / 2;
      if (fenw.quer(0, m) >= n / 2) {
        r = m;
      } else {
        l = m + 1;
      }
    }
    int k = r;
    int cnt = fenw.quer(0, k), prev = fenw.quer(0, k - 1);
    if (cnt == n / 2) {
      done = true;
    }
    while (ptr < q && (done == true || quer[ptr][0] == it)) {
      parr(quer[ptr]);
      l = 0, r = n - 1;
      while (r > l) {
        int m = (l + r) / 2;
        if (fenw.quer(0, m) >= quer[ptr][1] + 1) {
          r = m;
        } else {
          l = m + 1;
        }
      }
      pv(l);
      int prv = fenw.quer(0, l - 1);
      pv(prv);
      ans[quer[ptr][2]] = a[at[l] + quer[ptr][1] - prv];
      ptr++;
    }
    fenw.add(k, -(cnt - n / 2));
    for (int i = at[k] + n / 2 - prev; i < at[k] + cnt - prev; i = nl[i]) {
      fenw.add(a[i], min(at[k] + cnt - prev, nl[i]) - i);
    }
  }
  for (int i = 0; i < q; i++) {
    cout << ans[i] + 1 << '\n';
  }
}

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