結果
問題 | No.2930 Larger Mex |
ユーザー |
![]() |
提出日時 | 2024-10-12 15:06:56 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 536 ms / 2,000 ms |
コード長 | 1,421 bytes |
コンパイル時間 | 5,078 ms |
コンパイル使用メモリ | 314,608 KB |
実行使用メモリ | 18,816 KB |
最終ジャッジ日時 | 2024-10-12 15:07:20 |
合計ジャッジ時間 | 22,042 ms |
ジャッジサーバーID (参考情報) |
judge / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/all> using namespace std; using namespace atcoder; #define int long long signed main(){ int N,M; cin >> N >> M; vector<int> A(N); for(int i=0;i<N;i++){ cin >> A[i]; } if(M==0){ for(int k=1;k<=N;k++){ cout << N-k+1 << endl; } return 0; } //k>=Mが必要. //長さkの連続部分列であって,0,1,2,...,M-1がすべて含まれる に言い換えられる //lを移動 -> rの最小値が求まれば良い //尺取りのノリ map<int,int> data; int r=-1; for(int R=0;R<N;R++){ if(A[R]<M){ data[A[R]]++; } if((int)(data.size())==M){ r=R+1; break; } } if((int)(data.size())!=M){ for(int k=1;k<=N;k++){ cout << 0 << endl; } return 0; } //[0,r)はok //長さr,r+1,...,Nに+1 //imos //1,2,...,Nに+1 vector<int> ans(N+1); ans[r-1]++; ans[N]--; for(int l=1;l<N;l++){ //l-1を削除 if(A[l-1]<M){ data[A[l-1]]--; if(data[A[l-1]]==0){ data.erase(A[l-1]); } } if((int)(data.size())==M){ ans[r-l-1]++; ans[N-l]--; continue; } while(r<N){ if(A[r]<M){ data[A[r]]++; } r++; if((int)(data.size())==M){ break; } } if((int)(data.size())==M){ //[l,r) ~ [l,N) //r-l ~ N-lに+1 ans[r-l-1]++; ans[N-l]--; } } vector<int> sum(N+1); sum[0]=0; for(int i=1;i<=N;i++){ sum[i]=sum[i-1]+ans[i-1]; } for(int i=1;i<=N;i++){ cout << sum[i] << endl; } }