結果

問題 No.2697 Range LIS Query
ユーザー maeshunmaeshun
提出日時 2024-03-22 22:45:46
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 7,427 ms / 10,000 ms
コード長 2,163 bytes
コンパイル時間 4,575 ms
コンパイル使用メモリ 287,808 KB
実行使用メモリ 117,440 KB
最終ジャッジ日時 2024-09-30 12:12:42
合計ジャッジ時間 72,788 ms
ジャッジサーバーID
(参考情報)
judge4 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

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

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define rep(i, n) for(int i=0;i<(n);++i)
#define rep1(i, n) for(int i=1;i<=(n);i++)
#define ll long long
using mint = modint998244353;
using P = pair<ll,ll>;
using lb = long double;
using T = tuple<ll, ll, ll>;
#ifdef LOCAL
# include <debug_print.hpp>
# define dbg(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
# define dbg(...) (static_cast<void>(0))
#endif
struct S {
vector<vector<int>> v;
int len;
};
S op(S a, S b){
S c;
c.v = vector<vector<int>>(5, vector<int>(5));
for(int i=1;i<=4;i++) for(int j=1;j<=4;j++){
c.v[i][j] = max(a.v[i][j],b.v[i][j]);
}
for(int i=1;i<=4;i++){
for(int j=i;j<=4;j++){
for(int k=j;k<=4;k++){
for(int l=k;l<=4;l++){
c.v[i][l] = max(c.v[i][l], a.v[i][j]+b.v[k][l]);
}
}
}
}
c.len = a.len + b.len;
return c;
}
S e(){
S c;
c.v = vector<vector<int>>(5, vector<int>(5));
c.len = 0;
return c;
}
S mapping(int f, S a) {
if(f==-1) return a;
a.v = vector<vector<int>>(5, vector<int>(5));
a.v[f][f] = a.len;
return a;
}
int composition(int f, int g) {
if(f==-1) return g;
return f;
}
int id(){
return -1;
}
int main()
{
int n;
cin >> n;
vector<int> a(n);
rep(i,n) cin >> a[i];
lazy_segtree<S, op, e,int, mapping, composition, id> seg(n);
rep(i,n){
S c;
c.v = vector<vector<int>>(5,vector<int>(5));
c.v[a[i]][a[i]] = 1;
c.len = 1;
seg.set(i,c);
}
int q;
cin >> q;
while(q--){
int t;
cin >> t;
if(t==1){
int l, r;
cin >> l >> r;
--l;
auto vs = seg.prod(l,r);
int ans = 0;
dbg(vs.v);
rep(i,5) rep(j,5) {
ans = max(ans, vs.v[i][j]);
}
cout<<ans<<endl;
}
else{
int l, r, x;
cin >> l >> r >> x;
--l;;
seg.apply(l,r,x);
}
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0