kojingharangの日記

Codeforces div2 190d - Non-Secret Cypher

22:46 |

• 数値 W[i], 0 <= i < N, N <= 4*10^5 が与えられる。0 <= i <= j < N な区間 [i, j] のうち同じ数字が K 個以上含まれるものの個数を求める。

• なんの DP? と思ったけど N が大きいので違うっぽい
• しゃくとり法
• 数値ごとに個数をカウントして最大のものが K になるまで区間の終わりを右にずらす
• K になったら、区間の終わり以降のすべての終わりポイントにて K 個以上なので終わりポイントの個数を足す
• 最大のものが K 未満になるまで区間の始まりを右にずらす。その間、同様に終わりポイントの個数を足す
• O(N)

• 本番では ans が int になってて WA. N(N+1)/2 なので最大 8*10^10 程度になるのだった。
• なんかもう全ての整数変数は long long でいいんじゃないかって気がしてくる

↓あとで Accepted

int main() {
	int N, K;
	cin>>N>>K;
	VI w(N);
	REP(i, N) cin>>w[i];
	
	int L=0, R=0; // [L, R)
	int maxi = -1;
	int maxv = 0;
	map<int, int> hi;
	ll ans = 0;
	
	while(1) {
		if(R==N) break;
		while(R<N && maxv<K) {
			R++;
			hi[w[R-1]]++;
			if(hi[w[R-1]] > maxv) {
				maxv = hi[w[R-1]];
				maxi = w[R-1];
			}
		}
		if(maxv<K) break;
		ans += N-R+1;
		//cout<<L<<" "<<R<<"  + "<<N-R+1<<endl;
		while(L<N-1 && maxv == K) {
			L++;
			hi[w[L-1]]--;
			if(w[L-1]==maxi) {maxv--;break;}
			ans += N-R+1;
		}
		//cout<<L<<" "<<R<<endl;
	}
	
	cout<<ans<<endl;
	return 0;
}

ツイートする