oj.uz

Submission #646863

# Submission time Handle Problem Language Result Execution time Memory
646863 2022-09-30T21:56:40 Z chenwz Abracadabra (CEOI22_abracadabra) C++11
0 / 100
 3000 ms 20652 KB 
// CEOI 2022 Day1 - Abracadabra
#include <bits/stdc++.h>
using namespace std;
using VI = vector<int>;
struct BIT {
  VI C;
  int n;
  BIT(int _n) : C(_n + 1), n(_n + 1) {}
  void add(int x, int v) {
    while (x < n) C[x] += v, x += x & -x;
  }
  int sum(int x) {
    int ret = 0;
    while (x) ret += C[x], x -= x & -x;
    return ret;
  }
  int kth(int x) {
    int pos = 0;
    for (int b = 1 << 17; b >= 0; b >>= 1)
      if (pos + b < n && C[pos + b] < x) pos += b, x -= C[pos];
    return pos + 1;
  }
};
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int N, q;
  cin >> N >> q;
  BIT S(N);
  VI A(N), P(N + 1), Ans(q);
  vector<vector<pair<int, int>>> v(N + 1);
  for (int i = 0; i < N; i++) cin >> A[i], P[A[i]] = i;
  for (int i = 0, t, x; i < q; i++) {
    cin >> t >> x, t = min(t, N);
    if (t == 0)
      Ans[i] = A[x - 1];
    else
      v[t].emplace_back(x - 1, i);
  }
  VI nxt(N), ds(N + 1);
  auto SetVal = [&](int x, int v) { S.add(x, v - ds[x]), ds[x] = v; };
  for (int i = 0; i < N;) {
    int j = i + 1;
    while (j < N && A[j] < A[i]) j++;
    SetVal(A[i], j - i), i = j;
  }
  VI v2;
  for (int i = N - 1; i >= 0; i--) {
    while (!v2.empty() && A[v2.back()] < A[i]) v2.pop_back();
    nxt[i] = !v2.empty() ? v2.back() : N, v2.push_back(i);
  }
  for (int i = 1; i <= N; i++) {
    int itf = S.kth(N / 2 + 1), its = ds[itf], sum = S.sum(itf - 1);
    if (sum < N / 2) {
      int l = P[itf], r = l + its;
      SetVal(A[l], N / 2 - sum);
      l += N / 2 - sum;
      for (int i = l; i < r; i = nxt[i]) SetVal(A[i], min(r, nxt[i]) - i);
    }
    for (auto p : v[i]) {
      int pos = p.first, idx = p.second, qos = S.kth(pos + 1),
          sum = S.sum(qos - 1);
      Ans[idx] = A[P[qos] + pos - sum];
    }
  }
  for (int x : Ans) cout << x << "\n";
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3073 ms 14564 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3075 ms 20652 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3075 ms 7104 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3073 ms 14564 KB Time limit exceeded
2 Halted 0 ms 0 KB -