結果

問題 No.2697 Range LIS Query
ユーザー 沙耶花沙耶花
提出日時 2024-03-22 22:02:34
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 452 ms / 10,000 ms
コード長 1,574 bytes
コンパイル時間 4,796 ms
コンパイル使用メモリ 269,376 KB
実行使用メモリ 28,144 KB
最終ジャッジ日時 2024-09-30 11:33:42
合計ジャッジ時間 10,288 ms
ジャッジサーバーID
(参考情報)
judge3 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

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

#include <stdio.h>
#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using namespace atcoder;
using mint = modint998244353;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf32 1000000001
#define Inf64 1000000000000000001
using A = pair<array<array<int,4>,4>,int>;
A e(){
A ret;
rep(i,4){
for(int j=0;j<4;j++)ret.first[i][j] = 0;
}
ret.second = 0;
return ret;
}
A op(A a,A b){
A ret = e();
rep(i,4){
for(int j=i;j<4;j++){
for(int k=j;k<4;k++){
for(int l=k;l<4;l++){
ret.first[i][l] = max(ret.first[i][l],a.first[i][j] + b.first[k][l]);
}
}
}
}
ret.second = a.second + b.second;
return ret;
}
A mapping(int a,A b){
if(a==-1)return b;
rep(i,4){
rep(j,4)b.first[i][j] = 0;
}
b.first[a][a] =b.second;
return b;
}
int composition(int a,int b){
if(a==-1)return b;
return a;
}
int id(){
return -1;
}
int main(){
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
cin>>n;
vector<int> a(n);
rep(i,n){
cin>>a[i];
a[i]--;
}
lazy_segtree<A,op,e,int,mapping,composition,id> seg;
{
vector<A> ts;
rep(i,n){
A temp = e();
temp.first[a[i]][a[i]] = 1;
temp.second = 1;
ts.push_back(temp);
}
seg = lazy_segtree<A,op,e,int,mapping,composition,id>(ts);
}
int q;
cin>>q;
rep(_,q){
int t;
cin>>t;
int x,y;
cin>>x>>y;
if(t==1){
auto ret = seg.prod(x-1,y);
int ans = 0;
rep(i,4){
rep(j,4){
ans = max(ans,ret.first[i][j]);
}
}
cout<<ans<<endl;
}
else{
int z;
cin>>z;
seg.apply(x-1,y,z-1);
}
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0