Submission #1236102

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236102		avighna	Abracadabra (CEOI22_abracadabra)	C++20	40 / 100	554 ms	32944 KiB

Main

#include <bits/stdc++.h>

template <typename T> class segment_tree {
public:
  int _n, n;
  T idt;
  std::vector<T> seg;
  std::function<T(T, T)> f;

  segment_tree(int _n, std::function<T(T, T)> f = std::plus<T>(), T idt = T())
      : _n(_n), n(std::bit_ceil(uint32_t(_n))), idt(idt), f(f),
        seg(2 * n, idt) {}

  void set(int idx, T x) {
    for (seg[idx += n] = x, idx /= 2; idx > 0; idx /= 2) {
      seg[idx] = f(seg[2 * idx], seg[2 * idx + 1]);
    }
  }

  T query(int l, int r) {
    T ansL = idt, ansR = idt;
    for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
      if (l & 1)
        ansL = f(ansL, seg[l++]);
      if (r & 1)
        ansR = f(seg[--r], ansR);
    }
    return f(ansL, ansR);
  }

  int partition_point(int l, const std::function<bool(T)> &t) {
    T p = idt;
    for (l += n; t(f(p, seg[l])) and l & (l + 1); l /= 2) {
      if (l & 1)
        p = f(p, seg[l++]);
    }
    if (t(f(p, seg[l]))) {
      return _n;
    }
    while (l < n) {
      if (t(f(p, seg[l <<= 1])))
        p = f(p, seg[l++]);
    }
    return l - n;
  }
};

const int inf = 1e9;

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int n, q;
  std::cin >> n >> q;
  std::vector<int> a(n);
  for (int &i : a) {
    std::cin >> i;
    i--;
  }
  struct query {
    int t, i, idx;
  };
  std::vector<query> queries(q);
  for (int i = 0; i < q; ++i) {
    std::cin >> queries[i].t >> queries[i].i;
    queries[i].t = std::min(queries[i].t, n);
    queries[i].i--;
    queries[i].idx = i;
  }
  std::sort(queries.begin(), queries.end(), [](query a, query b) {
    return a.t < b.t;
  });

  std::stack<int> stk;
  std::vector<int> next(n, n);
  for (int i = n - 1; i >= 0; --i) {
    while (!stk.empty() and a[stk.top()] < a[i]) {
      stk.pop();
    }
    if (!stk.empty()) {
      next[i] = stk.top();
    }
    stk.push(i);
  }
  
  struct node {
    int l, sum, right_sum, active_cnt;

    node() : l(inf), sum(0), right_sum(0), active_cnt(0) {}
    node(int l, int sum, int right_sum, int active_cnt) : l(l), sum(sum), right_sum(right_sum), active_cnt(active_cnt) {}
  };
  auto combine = [&](node a, node b) {
    if (a.active_cnt == 0) {
      return b;
    }
    if (b.active_cnt == 0) {
      return a;
    }
    return node{b.l, a.sum + b.sum, b.right_sum, a.active_cnt + b.active_cnt};
  };
  std::vector<bool> active(n);
  segment_tree<node> st(n, combine, node{});
  for (int i = 0; i < n; i = next[i]) {
    active[a[i]] = true;
    st.set(a[i], {i, next[i] - i, next[i] - i, 1});
  }

  std::vector<int> ans(q);
  int cur_t = 0;
  for (auto &[t, i, idx] : queries) {
    while (cur_t < t) {
      node x = st.query(0, st.partition_point(0, [&](node t) {
        return t.sum <= n / 2;
      }));
      if (x.right_sum == 1) {
        cur_t++;
        continue;
      }
      int cur_idx = x.l - (x.sum - x.right_sum) + n / 2;
      int remaining = cur_idx - x.l;
      int obtained_so_far = 0;
      for (; cur_idx < n and !active[a[cur_idx]]; cur_idx = next[cur_idx]) {
        active[a[cur_idx]] = true;
        int next_idx = next[cur_idx];
        int del = next_idx - cur_idx;
        if (next_idx >= n or active[a[next_idx]]) {
          del = x.right_sum - remaining - obtained_so_far;
        }
        st.set(a[cur_idx], {cur_idx, del, del, 1});
        obtained_so_far += del;
      }
      st.set(a[x.l], {x.l, remaining, remaining, 1});
      cur_t++;
    }
    node x = st.query(0, st.partition_point(0, [&](node t) {
      return t.sum <= i;
    }));
    ans[idx] = a[x.l - (x.sum - x.right_sum) + i] + 1;
  }

  for (int &i : ans) {
    std::cout << i << '\n';
  }
}

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