結果
問題 | No.2697 Range LIS Query |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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);}}}