結果

問題 No.3167 [Cherry 7th Tune C] Cut in Queue
コンテスト
ユーザー tnakao0123
提出日時 2025-05-31 19:13:07
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 255 ms / 2,500 ms
コード長 2,469 bytes
コンパイル時間 958 ms
コンパイル使用メモリ 62,936 KB
実行使用メモリ 37,248 KB
最終ジャッジ日時 2025-05-31 19:13:24
合計ジャッジ時間 13,316 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 43
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:88:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   88 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
main.cpp:89:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   89 |   for (int i = 0; i < n; i++) scanf("%d", as + i), as[i]--;
      |                               ~~~~~^~~~~~~~~~~~~~
main.cpp:92:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   92 |   scanf("%d", &qn);
      |   ~~~~~^~~~~~~~~~~
main.cpp:95:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   95 |     scanf("%d", &op);
      |     ~~~~~^~~~~~~~~~~
main.cpp:96:23: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   96 |     if (op != 2) scanf("%d", &a), a--;
      |                  ~~~~~^~~~~~~~~~

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 3167.cc:  No.3167 [Cherry 7th Tune C] Cut in Queue - yukicoder
 */

#include<cstdio>
#include<vector>
#include<list>
#include<algorithm>
#include<utility>

using namespace std;

/* constant */

const int MAX_N = 300000;
const int MAX_QN = 300000;
const int MAX_M = MAX_N + MAX_QN;

/* typedef */

using lsti = list<int>;
using litr = lsti::iterator;
using pii = pair<int,int>;

template <typename T>
struct BIT {
  int n;
  vector<T> bits;
  
  BIT() {}
  BIT(int _n) { init(_n); }

  void init(int _n) {
    n = _n;
    bits.assign(n + 1, 0);
  }

  T sum(int x) {
    x = min(x, n);
    T s = 0;
    while (x > 0) {
      s += bits[x];
      x -= (x & -x);
    }
    return s;
  }

  void add(int x, T v) {
    if (x <= 0) return;
    while (x <= n) {
      bits[x] += v;
      x += (x & -x);
    }
  }
};

/* global variables */

int as[MAX_N];
pii ops[MAX_QN];
litr amp[MAX_M];
int aps[MAX_M], pas[MAX_M];
BIT<int> bit;

/* subroutines */

int findat(int m, int k) {
  int j0 = 0, j1 = m + 1;
  while (j0 + 1 < j1) {
    int j = (j0 + j1) / 2;
    if (bit.sum(j) > k) j1 = j;
    else j0 = j;
  }
  return j0;
}

void printv(int m) {
  for (int i = 0; i < m; i++)
    if (bit.sum(i + 1) > bit.sum(i)) printf(" %d", pas[i] + 1);
  putchar('\n');}


/* main */

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d", as + i), as[i]--;

  int qn;
  scanf("%d", &qn);
  for (int i = 0; i < qn; i++) {
    int op, a = -1;
    scanf("%d", &op);
    if (op != 2) scanf("%d", &a), a--;
    ops[i] = {op, a};
  }
  
  lsti ls;
  for (int i = 0; i < n; i++)
    amp[as[i]] = ls.insert(ls.end(), as[i]);
  for (int i = 0, b = n; i < qn; i++) {
    auto [op, a] = ops[i];
    if (op == 1) {
      auto lit = (a >= 0) ? amp[a] : ls.end();
      amp[b] = ls.insert(lit, b);
      b++;
    }
  }
  //for (auto a: ls) printf(" %d", a + 1); putchar('\n');

  int m = ls.size(), p = 0;
  for (auto a: ls) {
    aps[a] = p, pas[p] = a;
    p++;
  }

  bit.init(m);
  for (int i = 0; i < n; i++) bit.add(aps[as[i]] + 1, 1);

  for (int i = 0, b = n; i < qn; i++) {
    auto [op, a] = ops[i];
    //printf(" %d,%d\n", op, a + 1);

    if (op == 1) {
      int p = aps[b++];
      bit.add(p + 1, 1);
      //printv(m);
    }
    else if (op == 2) {
      int j = findat(m, 0);
      bit.add(j + 1, -1);
      //printv(m);
    }
    else {
      int j = findat(m, a);
      printf("%d\n", pas[j] + 1);
    }
  }
  
  return 0;
}
0