Submission #744619

#	Time	Username	Problem	Language	Result	Execution time	Memory
744619		tch1cherin	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	604 ms	48124 KiB

Main

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

struct fenwick {
  int size, logn;
  vector<int> fenw;

  fenwick(int n) : size(n), logn(__lg(n)), fenw(n + 1) {}

  void add(int i, int v) {
    for (i++; i <= size; i += i & -i) {
      fenw[i] += v;
    }
  }

  int query(int r) {
    int ans = 0;
    for (; r > 0; r -= r & -r) {
      ans += fenw[r];
    }
    return ans;
  }

  int lower_bound(int s) {
    int pos = 0;
    for (int delta = 1 << logn; delta > 0; delta /= 2) {
      if (pos + delta <= size && fenw[pos + delta] < s) {
        pos += delta;
        s -= fenw[pos];
      }
    }
    return pos;
  }
};

void solve() {
  int n, q;
  cin >> n >> q;
  vector<int> a(n);
  for (int &v : a) {
    cin >> v;
    v--;
  }
  int X = n;
  vector<vector<pair<int, int>>> queries(X);
  for (int i = 0; i < q; i++) {
    int t, p;
    cin >> t >> p;
    p--, t = min(t, X - 1);
    queries[t].emplace_back(i, p);
  }
  vector<int> nxt(n);
  stack<int> st;
  for (int i = n - 1; i >= 0; i--) {
    while (!st.empty() && a[st.top()] < a[i]) {
      st.pop();
    }
    nxt[i] = st.empty() ? n : st.top();
    st.push(i);
  }
  vector<int> answer(q);
  for (auto [i, p] : queries[0]) {
    answer[i] = a[p];  
  }
  fenwick fenw(n);
  vector<int> l(n), r(n);
  int pos = 0;
  while (pos != n) {
    int go = nxt[pos];
    if (pos < n / 2 && go > n / 2) {
      go = n / 2;
    }
    l[a[pos]] = pos;
    r[a[pos]] = go;
    fenw.add(a[pos], go - pos);
    pos = go;
  }
  for (int t = 1; t < X; t++) {
    for (auto [i, p] : queries[t]) {
      int j = fenw.lower_bound(p + 1);
      int sum = fenw.query(j + 1);
      answer[i] = a[r[j] - (sum - p)];
    }
    int j = fenw.lower_bound(n / 2); 
    int sum = fenw.query(j + 1);
    if (sum != 0) {
      int first = r[j] - (sum - n / 2), right = r[j];
      fenw.add(j, first - r[j]);
      r[j] = first;
      while (first != right) {
        int go = min(right, nxt[first]);
        l[a[first]] = first;
        r[a[first]] = go;
        fenw.add(a[first], go - first);
        first = go;
      }
    }
  }
  for (int v : answer) {
    cout << 1 + v << "\n";
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
}

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