제출 #440804

#제출 시각아이디문제언어결과실행 시간메모리
440804KULIKOLDLottery (CEOI18_lot)C++17
100 / 100
1430 ms6448 KiB
//#pragma GCC optimize ("O3") #include <bits/stdc++.h> using namespace std; typedef long long ll; #define endl '\n' const int DIM = 1E4+7; const int QZ = 1E2+7; int A[DIM],dp[DIM],ps[DIM]; pair<int,int> Q[DIM]; short int ans[DIM][QZ]; int solve(){ int n,l; cin>>n>>l; for(int i = 1;i<=n;++i){ cin>>A[i]; } int q; cin>>q; for(int i = 1;i<=q;++i){ cin>>Q[i].first; Q[i].second = i; } sort(Q+1,Q+1+q); for(int dist = 1;dist<=n;++dist){ dp[0] = 0; for(int i = 1;i+dist<=n;++i) dp[i] = dp[i-1]+(A[i]!=A[i+dist]); for(int i = 1;i+dist+l-1<=n;++i) { int cnt = dp[i + l - 1] - dp[i - 1]; int pos = lower_bound(Q + 1, Q + 1 + q, pair<int, int>{cnt, 0}) - Q; ans[i][pos]++; ans[i+dist][pos]++; } } for(int i = 1;i<=n;++i){ for(int j = 1;j<=q;++j){ ans[i][j] = ans[i][j-1]+ans[i][j]; } } for(int i = 1;i<=q;++i){ ps[Q[i].second] = i; } for(int i = 1;i<=q;++i){ for(int j = 1;j+l-1<=n;++j){ cout<<ans[j][ps[i]]<<' '; } cout<<endl; } return 1; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); assert(solve()); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...