結果

問題 No.2697 Range LIS Query
ユーザー shobonvipshobonvip
提出日時 2024-03-23 04:50:48
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 524 ms / 10,000 ms
コード長 2,340 bytes
コンパイル時間 4,111 ms
コンパイル使用メモリ 271,712 KB
実行使用メモリ 28,320 KB
最終ジャッジ日時 2024-09-30 13:03:40
合計ジャッジ時間 10,746 ms
ジャッジサーバーID
(参考情報)
judge1 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

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

#include<bits/stdc++.h>
using namespace std;
//* ATCODER
#include<atcoder/all>
using namespace atcoder;
typedef modint998244353 mint;
//*/
/* BOOST MULTIPRECISION
#include<boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
//*/
typedef long long ll;
#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)
template <typename T> bool chmin(T &a, const T &b) {
if (a <= b) return false;
a = b;
return true;
}
template <typename T> bool chmax(T &a, const T &b) {
if (a >= b) return false;
a = b;
return true;
}
template <typename T> T max(vector<T> &a){
assert(!a.empty());
T ret = a[0];
for (int i=0; i<(int)a.size(); i++) chmax(ret, a[i]);
return ret;
}
template <typename T> T min(vector<T> &a){
assert(!a.empty());
T ret = a[0];
for (int i=0; i<(int)a.size(); i++) chmin(ret, a[i]);
return ret;
}
template <typename T> T sum(vector<T> &a){
T ret = 0;
for (int i=0; i<(int)a.size(); i++) ret += a[i];
return ret;
}
struct S {
int dp[4][4];
int len;
S(): len(0) {
rep(i,0,4) rep(j,0,4) dp[i][j] = 0;
}
S(int x): len(1) {
rep(i,0,4) rep(j,0,4) dp[i][j] = 0;
dp[x][x] = 1;
}
S(int x, int l): len(l) {
rep(i,0,4) rep(j,0,4) dp[i][j] = 0;
dp[x][x] = l;
}
};
int score(S a){
int ret = -1e9;
rep(i,0,4){
rep(j,i,4){
chmax(ret, a.dp[i][j]);
}
}
return ret;
}
S e(){
return S();
}
S op(S a, S b){
S ret = S();
ret.len = a.len + b.len;
rep(i,0,4){
rep(j,i,4){
chmax(ret.dp[i][j], a.dp[i][j]);
chmax(ret.dp[i][j], b.dp[i][j]);
}
}
rep(i,0,4){
rep(j,i,4){
rep(k,j,4){
rep(l,k,4){
chmax(ret.dp[i][l], a.dp[i][j] + b.dp[k][l]);
}
}
}
}
return ret;
}
S mapping(int f, S x){
if (f == 4) return x;
return S(f, x.len);
}
int composition(int g, int f){
if (g == 4) return f;
return g;
}
int id(){return 4;}
int main(){
int n; cin >> n;
vector<int> a(n);
vector<S> init(n);
rep(i,0,n){
cin >> a[i];
a[i]--;
init[i] = S(a[i]);
}
lazy_segtree<S,op,e,int,mapping,composition,id> seg(init);
int q; cin >> q;
while(q--){
int t; cin >> t;
if (t == 1){
int l, r; cin >> l >> r;
l--;
cout << score(seg.prod(l, r)) << '\n';
}else{
int l, r; cin >> l >> r;
l--;
int x; cin >> x;
x--;
seg.apply(l,r,x);
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0