結果

問題 No.2223 Merged Med
ユーザー SSRSSSRS
提出日時 2023-02-17 21:51:20
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,661 ms / 7,000 ms
コード長 2,795 bytes
コンパイル時間 2,080 ms
コンパイル使用メモリ 184,160 KB
実行使用メモリ 15,000 KB
最終ジャッジ日時 2023-09-26 19:09:31
合計ジャッジ時間 29,947 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 1 ms
4,384 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 1 ms
4,376 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 2 ms
4,380 KB
testcase_13 AC 606 ms
6,488 KB
testcase_14 AC 344 ms
4,392 KB
testcase_15 AC 647 ms
13,052 KB
testcase_16 AC 1,238 ms
13,836 KB
testcase_17 AC 368 ms
8,848 KB
testcase_18 AC 316 ms
4,380 KB
testcase_19 AC 538 ms
6,176 KB
testcase_20 AC 1,588 ms
14,232 KB
testcase_21 AC 1,637 ms
14,372 KB
testcase_22 AC 1,644 ms
14,212 KB
testcase_23 AC 1,656 ms
14,336 KB
testcase_24 AC 1,638 ms
14,264 KB
testcase_25 AC 1,661 ms
14,172 KB
testcase_26 AC 1,655 ms
14,272 KB
testcase_27 AC 1,651 ms
14,304 KB
testcase_28 AC 1,632 ms
14,424 KB
testcase_29 AC 1,614 ms
14,268 KB
testcase_30 AC 793 ms
14,744 KB
testcase_31 AC 783 ms
13,576 KB
testcase_32 AC 80 ms
4,376 KB
testcase_33 AC 1,449 ms
14,224 KB
testcase_34 AC 1,226 ms
15,000 KB
testcase_35 AC 1,231 ms
13,608 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
const int INF = 10000000;
template <typename T>
struct segment_tree{
  int N;
  vector<T> ST;
  function<T(T, T)> f;
  T E;
  segment_tree(vector<T> A, function<T(T, T)> f, T E): f(f), E(E){
    int n = A.size();
    N = 1;
    while (N < n){
      N *= 2;
    }
    ST = vector<T>(N * 2 - 1, E);
    for (int i = 0; i < n; i++){
      ST[N - 1 + i] = A[i];
    }
    for (int i = N - 2; i >= 0; i--){
      ST[i] = f(ST[i * 2 + 1], ST[i * 2 + 2]);
    }
  }
  T operator [](int k){
    return ST[N - 1 + k];
  }
  void update(int k, T x){
    k += N - 1;
    ST[k] = x;
    while (k > 0){
      k = (k - 1) / 2;
      ST[k] = f(ST[k * 2 + 1], ST[k * 2 + 2]);
    }
  }
  T query(int L, int R, int i, int l, int r){
    if (r <= L || R <= l){
      return E;
    } else if (L <= l && r <= R){
      return ST[i];
    } else {
      int m = (l + r) / 2;
      return f(query(L, R, i * 2 + 1, l, m), query(L, R, i * 2 + 2, m, r));
    }
  }
  T query(int L, int R){
    return query(L, R, 0, 0, N);
  }
  T all(){
    return ST[0];
  }
};
int main(){
  int N, Q;
  cin >> N >> Q;
  vector<int> A(N);
  for (int i = 0; i < N; i++){
    cin >> A[i];
    A[i]--;
  }
  vector<int> l(Q), r(Q);
  for (int i = 0; i < Q; i++){
    cin >> l[i] >> r[i];
    l[i]--;
  }
  auto op = [](array<array<int, 3>, 3> A, array<array<int, 3>, 3> B){
    array<array<int, 3>, 3> C;
    for (int i = 0; i < 3; i++){
      for (int j = i; j < 3; j++){
        C[i][j] = INF;
        for (int k = i; k <= j; k++){
          C[i][j] = min(C[i][j], A[i][k] + B[k][j]);
        }
      }
    }
    return C;
  };
  array<array<int, 3>, 3> E = {{{0, INF, INF}, {INF, 0, INF}, {INF, INF, 0}}};
  array<array<int, 3>, 3> LESS_THAN_OR_EQUAL = {{{-1, 1, -1}, {INF, 0, -1}, {INF, INF, -1}}};
  array<array<int, 3>, 3> GREATER_THAN = {{{1, 1, 1}, {INF, 0, 1}, {INF, INF, 1}}};
  vector<vector<int>> add(N);
  for (int i = 0; i < N; i++){
    add[A[i]].push_back(i);
  }
  vector<int> tv(Q, N), fv(Q, -1);
  while (true){
    bool ok = true;
    vector<vector<int>> query(N);
    for (int i = 0; i < Q; i++){
      if (tv[i] - fv[i] > 1){
        ok = false;
        query[(tv[i] + fv[i]) / 2].push_back(i);
      }
    }
    if (ok){
      break;
    }
    segment_tree<array<array<int, 3>, 3>> ST(vector<array<array<int, 3>, 3>>(N, GREATER_THAN), op, E);
    for (int i = 0; i < N; i++){
      for (int j : add[i]){
        ST.update(j, LESS_THAN_OR_EQUAL);
      }
      for (int j : query[i]){
        array<array<int, 3>, 3> F = ST.query(l[j], r[j]);
        int res = min({F[0][0], F[0][1], F[0][2]});
        if (res < 0){
          tv[j] = i;
        } else {
          fv[j] = i;
        }
      }
    }
  }
  for (int i = 0; i < Q; i++){
    cout << tv[i] + 1 << endl;
  }
}
0