oj.uz

Submission #788632

# Submission time Handle Problem Language Result Execution time Memory
788632 2023-07-20T12:22:00 Z WLZ Abracadabra (CEOI22_abracadabra) C++17
0 / 100
 3000 ms 49740 KB 
#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.0

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

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 554 ms 48864 KB Output is correct
2 Correct 443 ms 49740 KB Output is correct
3 Correct 422 ms 39652 KB Output is correct
4 Correct 322 ms 32916 KB Output is correct
5 Correct 365 ms 34572 KB Output is correct
6 Correct 313 ms 31608 KB Output is correct
7 Correct 354 ms 39456 KB Output is correct
8 Correct 375 ms 38184 KB Output is correct
9 Correct 351 ms 33756 KB Output is correct
10 Correct 339 ms 35744 KB Output is correct
11 Correct 314 ms 29504 KB Output is correct
12 Correct 325 ms 29756 KB Output is correct
13 Correct 341 ms 34776 KB Output is correct
14 Correct 309 ms 30608 KB Output is correct
15 Correct 351 ms 36572 KB Output is correct
16 Correct 18 ms 3904 KB Output is correct
17 Correct 227 ms 32924 KB Output is correct
18 Correct 299 ms 27176 KB Output is correct
19 Correct 52 ms 9732 KB Output is correct
20 Execution timed out 3028 ms 10560 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2980 ms 11564 KB Output is correct
2 Execution timed out 3048 ms 11016 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

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