oj.uz

Submission #842260

# Submission time Handle Problem Language Result Execution time Memory
842260 2023-09-02T16:22:01 Z WLZ Abracadabra (CEOI22_abracadabra) C++17
40 / 100
 3000 ms 50076 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 3011 ms 23728 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 586 ms 49048 KB Output is correct
2 Correct 449 ms 50076 KB Output is correct
3 Correct 421 ms 39676 KB Output is correct
4 Correct 339 ms 34560 KB Output is correct
5 Correct 348 ms 34748 KB Output is correct
6 Correct 333 ms 33460 KB Output is correct
7 Correct 367 ms 39724 KB Output is correct
8 Correct 378 ms 38264 KB Output is correct
9 Correct 334 ms 34288 KB Output is correct
10 Correct 357 ms 36724 KB Output is correct
11 Correct 304 ms 30496 KB Output is correct
12 Correct 287 ms 31204 KB Output is correct
13 Correct 331 ms 35744 KB Output is correct
14 Correct 291 ms 31080 KB Output is correct
15 Correct 365 ms 36744 KB Output is correct
16 Correct 16 ms 3932 KB Output is correct
17 Correct 227 ms 32936 KB Output is correct
18 Correct 302 ms 28700 KB Output is correct
19 Correct 54 ms 9924 KB Output is correct
20 Correct 2845 ms 12140 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3011 ms 11716 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 3011 ms 23728 KB Time limit exceeded
2 Halted 0 ms 0 KB -