oj.uz

답안 #645626

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
645626 2022-09-27T14:15:47 Z Pety Abracadabra (CEOI22_abracadabra) C++14
0 / 100
 382 ms 32012 KB 
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int INF = 1e9;
const int MOD = 1e9 + 7;
const int M = 1e6+2;

int n, m, bit, p[200002], dr[200002];
pair<int, int>interval[200002];

int aib[200002];
int ans[M];

struct  queries{
  int p, t, i;
  bool operator < (const queries &other) {
    return t < other.t;
  }
} q[M];

void update (int x, int val) {
  for (int i = x; i <= n; i += (i & -i)) {
    aib[i] += val;
  }
}
int query (int x) {
  int s = 0;
  for (int i = x; i; i -= (i & -i))
     s += aib[i];
  return s;
}

int binary (int x) {
  int poz = 0;
  int s = 0;
  for (int i = (1 << bit); i; (i >>= 1)) {
    if (poz + i <= n && s + aib[poz + i] < x) {
      s += aib[poz + i];
      poz += i;
    }
  }
  return poz + 1;
}

int main () 
{
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> p[i];
  }
  for (int i = 1; i <= m; i++) {
    cin >> q[i].t >> q[i].p;
    q[i].i = i;
  }
  while ((1 << bit) <= n)
    bit++;
  bit--;
  sort(q + 1,q + m + 1);
  int ind = 1;
  while (ind <= m && q[ind].t == 0) {
    ans[q[ind].i] = p[q[ind].p];
    ind++;
  }
  stack<int>st;
  st.push(n + 1);
  p[n + 1] = n + 1;
  for (int i = n; i >= 1; i--) {
    while (p[st.top()] < p[i]) 
      st.pop();
    dr[i] = st.top();
    st.push(i);
  }
  int j = 1;
  while (j <= n) {
    if (j <= n / 2) {
      int l = j, r = min(n / 2, dr[j] - 1);
      update(p[j], r - l + 1);
      interval[p[j]] = {l, r};
      j = r + 1;
    }
    else {
      update(p[j], dr[j] - j);
      interval[p[j]] = {j, dr[j] - 1};
      j = dr[j];
    }
  }
  int time = 0;
  while (1) {
    time++;
    int val = binary(n / 2);
    int sum = query(val);
    while (ind <= m && q[ind].t == time) {
      int poz = binary(q[ind].p);
      int sum2 = query(poz - 1);
      ans[q[ind].i]  = p[interval[poz].first + q[ind].p - sum2 - 1];
      ind++;
    }
    if (sum == n / 2) 
      break;
    int overflow = sum - n / 2;
    update(val, -overflow);
    interval[val].second -= overflow;
    int j = interval[val].second + 1;
    while (j <= interval[val].second + overflow) {
      update(p[j], dr[j] - j);
      interval[p[j]] = {j, dr[j] - 1};
      j = dr[j];
    } 
  }
  while (ind <= m) {
    int poz = binary(q[ind].p);
    int sum2 = query(poz - 1);
    ans[q[ind].i]  = p[interval[poz].first + q[ind].p - sum2 - 1];
    ind++;
  }
  for (int i = 1; i <= m; i++)
    cout << ans[i] << "\n";
  return 0;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 298 ms 20800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 382 ms 32012 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 62 ms 5776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 298 ms 20800 KB Output isn't correct
2 Halted 0 ms 0 KB -