Submission #440804

#	Time	Username	Problem	Language	Result	Execution time	Memory
440804		KULIKOLD	Lottery (CEOI18_lot)	C++17	100 / 100	1430 ms	6448 KiB

lot

//#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;
}

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20