結果

問題 No.2697 Range LIS Query
ユーザー 00 Sakuda00 Sakuda
提出日時 2024-03-31 02:24:13
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 6,012 ms / 10,000 ms
コード長 1,256 bytes
コンパイル時間 2,973 ms
コンパイル使用メモリ 226,896 KB
実行使用メモリ 100,096 KB
最終ジャッジ日時 2024-09-30 17:48:52
合計ジャッジ時間 50,221 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
#include <atcoder/lazysegtree>
using namespace std;
using namespace atcoder;
vector<vector<int>> base(4, vector<int>(4, 0));
struct S{
vector<vector<int>> lis;
int size;
};
S op(S a, S b) {
vector<vector<int>> lis = base;
for (int i = 0;i < 4;i++) for (int j = i;j < 4;j++) for (int k = j;k < 4;k++) for (int l = k;l < 4;l++) {
lis[i][l] = max(lis[i][l], a.lis[i][j] + b.lis[k][l]);
}
return {lis, a.size + b.size};
}
S e() {
return {base, 0};
}
S mapping(int f, S x) {
if (f == -1) return x;
vector<vector<int>> lis = base;
lis[f][f] = x.size;
return S {lis, x.size};
}
int composition(int f, int g) {
if (f == -1) return g;
return f;
}
int id() {
return -1;
}
int main() {
int N;cin >> N;
vector<S> A(N + 1, {base, 1});
for (int i = 1;i <= N;i++) {
int a;cin >> a;
a--;
A[i].lis[a][a] = 1;
}
lazy_segtree<S, op, e, int, mapping, composition, id> seg(A);
int Q;cin >> Q;
while (Q--) {
int op;cin >> op;
if (op == 2) {
int l, r, x;cin >> l >> r >> x;
seg.apply(l, r + 1, x - 1);
continue;
}
int l,r;cin >> l >> r;
int ans = 0;
auto res = seg.prod(l, r + 1);
for (int i = 0;i < 4;i++) for (int j = i;j < 4;j++) ans = max(ans, res.lis[i][j]);
cout << ans << endl;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0