結果
問題 | No.2697 Range LIS Query |
ユーザー |
![]() |
提出日時 | 2024-04-05 09:27:18 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 210 ms / 10,000 ms |
コード長 | 2,064 bytes |
コンパイル時間 | 1,581 ms |
コンパイル使用メモリ | 123,988 KB |
実行使用メモリ | 20,392 KB |
最終ジャッジ日時 | 2024-10-01 00:57:50 |
合計ジャッジ時間 | 5,151 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 |
ソースコード
#include <iostream>#include <vector>using namespace std;#include <atcoder/lazysegtree>struct S {int n = 0;int a11 = 0;int a12 = 0;int a13 = 0;int a14 = 0;int a22 = 0;int a23 = 0;int a24 = 0;int a33 = 0;int a34 = 0;int a44 = 0;int longest() const { return max({a11, a12, a13, a14, a22, a23, a24, a33, a34, a44}); }};S gen1(int n) { return S{n, n, n, n, n, 0, 0, 0, 0, 0, 0}; }S gen2(int n) { return S{n, 0, n, n, n, n, n, n, 0, 0, 0}; }S gen3(int n) { return S{n, 0, 0, n, n, 0, n, n, n, n, 0}; }S gen4(int n) { return S{n, 0, 0, 0, n, 0, 0, n, 0, n, n}; }S op(S l, S r) {return {l.n + r.n,l.a11 + r.a11,max({l.a11 + r.a12, l.a12 + r.a22}),max({l.a11 + r.a13, l.a12 + r.a23, l.a13 + r.a33}),max({l.a11 + r.a14, l.a12 + r.a24, l.a13 + r.a34, l.a14 + r.a44}),l.a22 + r.a22,max({l.a22 + r.a23, l.a23 + r.a33}),max({l.a22 + r.a24, l.a23 + r.a34, l.a24 + r.a44}),l.a33 + r.a33,max({l.a33 + r.a34, l.a34 + r.a44}),l.a44 + r.a44,};}S e() { return S{}; }S gen(int a, int n) {if (a == 1) return gen1(n);if (a == 2) return gen2(n);if (a == 3) return gen3(n);if (a == 4) return gen4(n);assert(false);}using F = int;S mapping(F f, S x) {if (!f) return x;return gen(f, x.n);}F composition(F f, F g) {if (!f) return g;return f;}F id() { return 0; }int main() {cin.tie(nullptr)->sync_with_stdio(false);int N;cin >> N;vector<S> init;for (int i = 0; i < N; ++i) {int a;cin >> a;init.push_back(gen(a, 1));}atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(init);int Q;cin >> Q;while (Q--) {int tp, l, r;cin >> tp >> l >> r;--l;if (tp == 1) {cout << seg.prod(l, r).longest() << '\n';} else {int x;cin >> x;seg.apply(l, r, x);}}}