結果

問題 No.2697 Range LIS Query
ユーザー KudeKude
提出日時 2024-03-22 22:41:34
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 189 ms / 10,000 ms
コード長 2,624 bytes
コンパイル時間 3,590 ms
コンパイル使用メモリ 284,884 KB
実行使用メモリ 26,792 KB
最終ジャッジ日時 2024-09-30 12:06:54
合計ジャッジ時間 6,601 ms
ジャッジサーバーID
(参考情報)
judge3 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

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);
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0