結果

問題 No.2697 Range LIS Query
ユーザー KudeKude
提出日時 2024-03-22 22:41:34
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 223 ms / 10,000 ms
コード長 2,624 bytes
コンパイル時間 3,801 ms
コンパイル使用メモリ 283,420 KB
実行使用メモリ 26,848 KB
最終ジャッジ日時 2024-03-22 22:41:48
合計ジャッジ時間 7,292 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
6,676 KB
testcase_01 AC 2 ms
6,676 KB
testcase_02 AC 2 ms
6,676 KB
testcase_03 AC 6 ms
6,676 KB
testcase_04 AC 7 ms
6,676 KB
testcase_05 AC 6 ms
6,676 KB
testcase_06 AC 193 ms
26,848 KB
testcase_07 AC 193 ms
26,848 KB
testcase_08 AC 190 ms
26,848 KB
testcase_09 AC 142 ms
26,848 KB
testcase_10 AC 143 ms
26,848 KB
testcase_11 AC 142 ms
26,848 KB
testcase_12 AC 121 ms
25,952 KB
testcase_13 AC 151 ms
24,696 KB
testcase_14 AC 181 ms
24,856 KB
testcase_15 AC 223 ms
26,848 KB
testcase_16 AC 222 ms
26,848 KB
testcase_17 AC 218 ms
26,848 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
namespace {
#pragma GCC diagnostic ignored "-Wunused-function"
#include<atcoder/all>
#pragma GCC diagnostic warning "-Wunused-function"
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }
using ll = long long;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;

struct S {
  int len, v00,v01,v02,v03,v04,v11,v12,v13,v14,v22,v23,v24,v33,v34,v44;
};
S op(S x, S y) {
  return S{
    x.len + y.len,
    max({x.v00+y.v00}),
    max({x.v01+y.v11,x.v00+y.v01}),
    max({x.v02+y.v22,x.v01+y.v12,x.v00+y.v02}),
    max({x.v03+y.v33,x.v02+y.v23,x.v01+y.v13,x.v00+y.v03}),
    max({x.v04+y.v44,x.v03+y.v34,x.v02+y.v24,x.v01+y.v14,x.v00+y.v04}),
    max({x.v11+y.v11}),
    max({x.v12+y.v22,x.v11+y.v12}),
    max({x.v13+y.v33,x.v12+y.v23,x.v11+y.v13}),
    max({x.v14+y.v44,x.v13+y.v34,x.v12+y.v24,x.v11+y.v14}),
    max({x.v22+y.v22}),
    max({x.v23+y.v33,x.v22+y.v23}),
    max({x.v24+y.v44,x.v23+y.v34,x.v22+y.v24}),
    max({x.v33+y.v33}),
    max({x.v34+y.v44,x.v33+y.v34}),
    max({x.v44+y.v44})
  };
}
S e() { return S{}; }

using F = int;
F id() {
  return -1;
}
F composition(F f, F g) {
  if (f == -1) return g;
  else return f;
}
S mapping(F f, S x) {
  if (f == -1) return x;
  S res{};
  res.len = x.len;
  if (f == 0) res.v00 = res.len;
  else if (f == 1) res.v01 = res.v11 = res.len;
  else if (f == 2) res.v02 = res.v12 = res.v22 = res.len;
  else if (f == 3) res.v03 = res.v13 = res.v23 = res.v33 = res.len;
  else res.v04 = res.v14 = res.v24 = res.v34 = res.v44 = res.len;
  return res;
}

} int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  VI a(n);
  rep(i, n) cin >> a[i], a[i]--;
  vector<S> init(n);
  rep(i, n) {
    S x{};
    x.len = 1;
    init[i] = mapping(a[i], x);
  }
  lazy_segtree<S, op, e, F, mapping, composition, id> seg(init);

  int q;
  cin >> q;
  while (q--) {
    int type;
    cin >> type;
    if (type == 1) {
      int l, r;
      cin >> l >> r;
      l--;
      auto s = seg.prod(l, r);
      int ans = max({s.v00, s.v02, s.v03, s.v04});
      cout << ans << '\n';
    } else {
      int l, r, x;
      cin >> l >> r >> x;
      l--;
      x--;
      seg.apply(l, r, x);
    }
  }
}
0