Submission #1236144

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236144		avighna	Abracadabra (CEOI22_abracadabra)	C++20	100 / 100	742 ms	32984 KiB

Main

#include <bits/stdc++.h>

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

  segment_tree(uint32_t _n, std::function<T(T, T)> f, T idt)
    : n(std::bit_ceil(_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 _r) {
    T ansL = idt, ansR = idt;
    for (int l = n, r = _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++]);
    }
    while (l < n) {
      if (t(f(p, seg[l <<= 1]))) p = f(p, seg[l++]);
    }
    return l - n;
  }

  T operator[](int i) {
    return query(partition_point(0, [&](T t) {
      return t.sum <= i;
    }));
  }
};

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;

    node() : l(0), sum(0), right_sum(0), active(0) {}
    node(int l, int sum, int right_sum, int active) : l(l), sum(sum), right_sum(right_sum), active(active) {}
  };
  auto combine = [&](node a, node b) {
    if (a.active == 0) {
      return b;
    }
    if (b.active == 0) {
      return a;
    }
    return node{b.l, a.sum + b.sum, b.right_sum, a.active + b.active};
  };
  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[n / 2];
      int remaining = n / 2 - (x.sum - x.right_sum);
      if (remaining == 0) {
        cur_t = n;
        break;
      }
      int cur_idx = x.l - (x.sum - x.right_sum) + n / 2;
      int obtained_so_far = 0;
      bool in_bounds = true;
      while (in_bounds) {
        active[a[cur_idx]] = true;
        int next_idx = next[cur_idx];
        in_bounds &= next_idx < n and !active[a[next_idx]];
        int del = in_bounds ? next_idx - cur_idx : x.right_sum - remaining - obtained_so_far;
        st.set(a[cur_idx], {cur_idx, del, del, 1});
        obtained_so_far += del;
        cur_idx = next_idx;
      }
      st.set(a[x.l], {x.l, remaining, remaining, 1});
      cur_t++;
    }
    node x = st[i];
    ans[idx] = a[x.l - (x.sum - x.right_sum) + i] + 1;
  }

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

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