Submission #842260

#	Time	Username	Problem	Language	Result	Execution time	Memory
842260		WLZ	Abracadabra (CEOI22_abracadabra)	C++17	40 / 100	3011 ms	50076 KiB

Main

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

const int INF = 0x3f3f3f3f;

/** Does not work with 0-based indexing */
class fenwick_tree {
  private: 
    int n;
    vector<int> fenw;
    #ifdef DEBUG
    vector<int> debug;
    #endif
  public:
    fenwick_tree() {}

    fenwick_tree(int _n) : n(_n) {
      fenw.assign(n, 0);
      #ifdef DEBUG
      debug.assign(n, 0);
      #endif
    }

    /** Updates fenw[idx] to x. Gets stuck in infinite loop if idx = 0 */
    void update(int idx, int x) {
      #ifdef DEBUG
      debug[idx] += x;
      #endif
      while (idx < n) {
        fenw[idx] += x;
        idx += (idx & -idx);
      }
    }

    /** Returns sum of all elements in fenw[1..idx]. Returns 0 if idx = 0 */
    int query(int idx) {
      int ans = 0;
      while (idx > 0) {
        ans += fenw[idx];
        idx -= (idx & -idx);
      }
      return ans;
    }

    /** Returns smallest idx such that fenw[idx] >= x. Returns n if there is no such element. Assumes all current elements are nonnegative */
    int lower_bound(int x) {
      int idx = 0, cur = 0;
      for (int i = ceil(log2(n + 1)); i >= 0; i--) {
        if (idx + (1 << i) < n && cur + fenw[idx + (1 << i)] < x) {
          idx += (1 << i);
          cur += fenw[idx];
        }
      }
      return idx + 1;
    }
};

int n, q;
bool start = true, stopped = false;
vector<int> a, next_larger;
map<int, pair<int, int> > blocks;
fenwick_tree fenw;

void init_deck() {
  int prev = 0;
  for (int i = 1; i < n / 2; i++) {
    if (a[i] > a[prev]) {
      blocks[a[prev]] = {prev, i - 1};
      prev = i;
    }
  }
  blocks[a[prev]] = {prev, n / 2 - 1};
  prev = n / 2;
  for (int i = n / 2 + 1; i < n; i++) {
    if (a[i] > a[prev]) {
      blocks[a[prev]] = {prev, i - 1};
      prev = i;
    }
  }
  blocks[a[prev]] = {prev, n - 1};
  for (auto &p : blocks) fenw.update(p.first, p.second.second - p.second.first + 1);
  stack<int> st;
  for (int i = n - 1; i >= 0; i--) {
    while (!st.empty() && a[st.top()] < a[i]) st.pop();
    if (st.empty()) next_larger[i] = INF;
    else next_larger[i] = st.top();
    st.push(i);
  }
} 

void shuffle_cards() {
  if (stopped) return;
  if (start) {
    init_deck();
    start = false;
    return;
  }
  int mid = fenw.lower_bound(n / 2 + 1);
  int l = fenw.query(mid - 1);
  if (l == n / 2) {
    stopped = true;
    return;
  }
  int l_idx = blocks[mid].first + n / 2 - l;
  for (int i = l_idx; i <= blocks[mid].second; i = next_larger[i]) {
    blocks[a[i]] = {i, min(next_larger[i] - 1, blocks[mid].second)};
    fenw.update(a[i], min(next_larger[i] - 1, blocks[mid].second) - i + 1);
  }
  fenw.update(mid, l_idx - 1 - blocks[mid].second); blocks[mid].second = l_idx - 1; 
}

int get_card(int idx) {
  if (start) return a[idx - 1];
  int block = fenw.lower_bound(idx);
  return a[blocks[block].first + idx - fenw.query(block - 1) - 1];
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> q;
  a.resize(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  vector< tuple<int, int, int> > queries;
  for (int i = 0; i < q; i++) {
    int t, idx;
    cin >> t >> idx;
    queries.push_back({t, idx, i});
  }
  sort(queries.begin(), queries.end());
  int cur = 0;
  vector<int> ans(q);  
  fenw = fenwick_tree(n + 1);
  next_larger.resize(n);
  for (auto &p : queries) {
    int t = get<0>(p), idx = get<1>(p);
    for (; cur < t; cur++) shuffle_cards();
    ans[get<2>(p)] = get_card(idx);
  }
  for (auto &x : ans) cout << x << '\n';
  return 0;
}

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