結果

問題 No.2223 Merged Med
ユーザー SSRSSSRS
提出日時 2023-02-17 21:48:50
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,784 bytes
コンパイル時間 2,199 ms
コンパイル使用メモリ 182,768 KB
実行使用メモリ 15,184 KB
最終ジャッジ日時 2023-09-26 19:05:18
合計ジャッジ時間 31,300 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 AC 2 ms
4,380 KB
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 AC 785 ms
13,496 KB
testcase_32 AC 80 ms
4,384 KB
testcase_33 WA -
testcase_34 WA -
testcase_35 AC 1,245 ms
13,436 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][2]);
        if (res < 0){
          tv[j] = i;
        } else {
          fv[j] = i;
        }
      }
    }
  }
  for (int i = 0; i < Q; i++){
    cout << tv[i] + 1 << endl;
  }
}
0