結果
問題 | No.2697 Range LIS Query |
ユーザー |
👑 |
提出日時 | 2024-03-22 22:56:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 7,747 ms / 10,000 ms |
コード長 | 2,617 bytes |
コンパイル時間 | 5,326 ms |
コンパイル使用メモリ | 269,136 KB |
最終ジャッジ日時 | 2025-02-20 12:22:15 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/all> #define rep(i,n) for(int i=0;i<n;i++) using namespace std; using namespace atcoder; typedef long long ll; typedef vector<int> vi; typedef vector<long long> vl; typedef vector<vector<int>> vvi; typedef vector<vector<long long>> vvl; typedef long double ld; typedef pair<int, int> P; ostream& operator<<(ostream& os, const modint& a) {os << a.val(); return os;} template <int m> ostream& operator<<(ostream& os, const static_modint<m>& a) {os << a.val(); return os;} template <int m> ostream& operator<<(ostream& os, const dynamic_modint<m>& a) {os << a.val(); return os;} template<typename T> istream& operator>>(istream& is, vector<T>& v){int n = v.size(); assert(n > 0); rep(i, n) is >> v[i]; return is;} template<typename U, typename T> ostream& operator<<(ostream& os, const pair<U, T>& p){os << p.first << ' ' << p.second; return os;} template<typename T> ostream& operator<<(ostream& os, const vector<T>& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : " "); return os;} template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : ""); return os;} template<typename T> void chmin(T& a, T b){a = min(a, b);} template<typename T> void chmax(T& a, T b){a = max(a, b);} int M = 4; struct S{ vector<vector<int>> v; int s; }; S op(S a, S b){ vector<vector<int>> v(4, vector<int>(4)); rep(ia, 4) for(int ja = ia; ja < 4; ja++){ for(int ib = ja; ib < 4; ib++) for(int jb = ib; jb < 4; jb++){ chmax(v[ia][jb], a.v[ia][ja] + b.v[ib][jb]); } } S res = {v, a.s + b.s}; return res; } S e(){ return (S){vector<vector<int>>(4, vector<int>(4)), 0}; } using F = int; int INF = 1001001001; S mapping(F f, S x){ if(f == INF) return x; vector<vector<int>> v(4, vector<int>(4)); v[f][f] = x.s; return S{v, x.s}; } F composition(F f, F g){ if(f == INF) return g; else return f; } F id(){ return INF; } vector<vector<vector<int>>> memo(4, vector<vector<int>>(4, vector<int>(4))); int main(){ rep(i, 4) memo[i][i][i] = 1; int n; cin >> n; vector<int> a(n); cin >> a; rep(i, n) a[i]--; vector<S> init(n); rep(i, n){ init[i].v = memo[a[i]]; init[i].s = 1; } lazy_segtree<S, op, e, F, mapping, composition, id> seg(init); int q; cin >> q; rep(i, q){ int t, l, r; cin >> t >> l >> r; l--; r--; if(t == 1){ auto res = seg.prod(l, r + 1); int ans = 0; rep(i, 4) for(int j = i; j < 4; j++) chmax(ans, res.v[i][j]); cout << ans << "\n"; } if(t == 2){ int x; cin >> x; x--; seg.apply(l, r + 1, x); } } return 0; }