Codeforces 180E Cubes

問題

n個の数列がある。
この中からk個以下の数字を削除して、連続する同一の数字の長さを最大にしたい。
その最大値を求めよ。

制約条件

n≦2 * 10^5

方針

数字ごとに、その数字が出てくるインデックスを取り出す。
そしたら、その数字ごとに尺取すればいい。

すなわち、消す数がk個以下である間範囲を伸ばし続けるような尺取。
これで時間・空間計算量がO(n)で答えが求まる。

ソースコード

int n, m, k, a[200000], ans;
vi v[100010];

int main(){
	cin >> n >> m >> k;
	rep(i, n){
		cin >> a[i];
		v[a[i]].pb(i);
	}
	
	rep(it, 100010){
		vi &b = v[it];
		int i = 0, j = 0, skip = 0;
		for(; i < b.size(); i++){
			
			while(j < b.size()){
				if(i != j && skip + b[j] - b[j-1] - 1 > k) break;
				if(i < j) skip += b[j] - b[j-1] - 1;
				j++;
			}
			ans = max(ans, j - i);
			
			if(i + 1 < j) skip -= b[i+1] - b[i] - 1;
		}
	}
	cout << ans << endl;
	
	return 0;
}