제출 #971688

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
971688		nguyentunglam	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	651 ms	77524 KiB

Main

#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;

const int N = 1e6 + 10;

int n, q;

int a[N], ans[N], nxt[N], rev_a[N], ed[N];

vector<pair<int, int> > query[N];

int T[N << 2];

void up(int s, int l, int r, int pos, int val) {
  if (l == r) {
    T[s] = val;
    return;
  }
  int mid = l + r >> 1;
  if (pos <= mid) up(s << 1, l, mid, pos, val);
  else up(s << 1 | 1, mid + 1, r, pos, val);
  T[s] = T[s << 1] + T[s << 1 | 1];
}

int get(int s, int l, int r, int from, int to) {
  if (l > to || r < from) return 0;
  if (from <= l && r <= to) return T[s];
  int mid = l + r >> 1;
  return get(s << 1, l, mid, from, to) + get(s << 1 | 1, mid + 1, r, from, to);
}

int walk_on_tree (int s, int l, int r, int val) {
  if (l == r) return l;
  int mid = l + r >> 1;
  if (T[s << 1] >= val) return walk_on_tree(s << 1, l, mid, val);
  return walk_on_tree(s << 1 | 1, mid + 1, r, val - T[s << 1]);
}

int32_t main() {
  #define task ""

  cin.tie(0) -> sync_with_stdio(0);

  if (fopen("task.inp", "r")) {
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
  }

  if (fopen(task".inp", "r")) {
    freopen (task".inp", "r", stdin);
    freopen (task".out", "w", stdout);
  }

  cin >> n >> q;

  for(int i = 1; i <= n; i++) cin >> a[i], rev_a[a[i]] = i;

  for(int i = 1; i <= q; i++) {
    int t, x; cin >> t >> x;
    query[min(n, t)].emplace_back(x, i);
  }

//  exit(0);
  stack<int> st;
  for(int i = n; i >= 1; i--) {
    while (!st.empty() && a[st.top()] < a[i]) st.pop();
    nxt[i] = st.empty() ? n + 1 : st.top();
    st.push(i);
  }

  auto add = [&] (int start, int reach) {
    int u = start;
    while (u <= reach) {
      ed[u] = min(nxt[u] - 1, reach);
      up(1, 1, n, a[u], ed[u] - u + 1);
      u = ed[u] + 1;
    }
  };

  add(1, n);

  for(int turn = 0, change = 1; turn <= n; turn++) {
    for(auto [x, i] : query[turn]) {
      int pos = walk_on_tree(1, 1, n, x);
      int pre = get(1, 1, n, 1, pos - 1);
      pos = rev_a[pos];
      ans[i] = a[pos + x - pre - 1];
    }
    if (change == 0) continue;
    int pos = walk_on_tree(1, 1, n, n / 2);
    int pre = get(1, 1, n, 1, pos - 1);
    pos = rev_a[pos];
    if (pre + ed[pos] - pos + 1 == n / 2) {
      change = 0;
      continue;
    }
    int old = ed[pos];
    ed[pos] = pos + n / 2 - pre - 1;
    up(1, 1, n, a[pos], ed[pos] - pos + 1);
    add(ed[pos] + 1, old);
  }

  for(int i = 1; i <= q; i++) cout << ans[i] << endl;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'void up(int, int, int, int, int)':
Main.cpp:21:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |   int mid = l + r >> 1;
      |             ~~^~~
Main.cpp: In function 'int get(int, int, int, int, int)':
Main.cpp:30:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |   int mid = l + r >> 1;
      |             ~~^~~
Main.cpp: In function 'int walk_on_tree(int, int, int, int)':
Main.cpp:36:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |   int mid = l + r >> 1;
      |             ~~^~~
Main.cpp: In function 'int32_t main()':
Main.cpp:47:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     freopen("task.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:48:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     freopen("task.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:52:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |     freopen (task".inp", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:53:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |     freopen (task".out", "w", stdout);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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