結果

問題 No.2697 Range LIS Query
ユーザー 沙耶花沙耶花
提出日時 2024-03-22 22:02:34
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 460 ms / 10,000 ms
コード長 1,574 bytes
コンパイル時間 4,946 ms
コンパイル使用メモリ 269,912 KB
実行使用メモリ 29,652 KB
最終ジャッジ日時 2024-03-22 22:02:45
合計ジャッジ時間 10,859 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,676 KB
testcase_01 AC 2 ms
6,676 KB
testcase_02 AC 2 ms
6,676 KB
testcase_03 AC 11 ms
6,676 KB
testcase_04 AC 11 ms
6,676 KB
testcase_05 AC 12 ms
6,676 KB
testcase_06 AC 420 ms
29,652 KB
testcase_07 AC 390 ms
29,652 KB
testcase_08 AC 392 ms
29,652 KB
testcase_09 AC 396 ms
29,652 KB
testcase_10 AC 395 ms
29,652 KB
testcase_11 AC 414 ms
29,652 KB
testcase_12 AC 233 ms
27,576 KB
testcase_13 AC 274 ms
27,348 KB
testcase_14 AC 366 ms
27,372 KB
testcase_15 AC 429 ms
29,652 KB
testcase_16 AC 460 ms
29,652 KB
testcase_17 AC 435 ms
29,652 KB
権限があれば一括ダウンロードができます

ソースコード

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;
}
0