Submission #1090144

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090144		ZeroCool	Lottery (CEOI18_lot)	C++14	100 / 100	334 ms	8528 KiB

lot

#include <bits/stdc++.h>

using namespace std;

//#define int long long
#define ll long long
#define ar array

//const int INF = 1e17;
const int N = 1e4 + 5;
const int Q = 105;
const int MOD = 1e9 + 7;

int A[N], que[N], B[Q], id[N], pref[N], ans[N][Q];
                
signed main(){ios_base::sync_with_stdio(false);cin.tie(0);
    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>>que[i];
        //--que[i];
        B[i] = que[i];
    }
    sort(B + 1, B + q + 1);
    int j = 0;
    for(int i = 1;i <= n;i++){
        while(j <= q && B[j] < i)j++;
        id[i] = j;
        //cout<<id[i]<<" ";
    }
   // cout<<'\n';
    for(int d = 1;d <= n;d++){
        for(int i = 1;i + d <= n;i++){
            pref[i] = (A[i] != A[i + d]);
            if(i)pref[i] += pref[i - 1];
        }
        for(int i = 1;i + d + l - 1 <= n;i++){
            int k = pref[i + l - 1];
            if(i)k -= pref[i - 1];
            ans[i][id[k]]++;
            ans[i + d][id[k]]++;
        }
    }
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= q;j++)ans[i][j] += ans[i][j - 1];
    }
    for(int i = 1;i <= q;i++){
        for(int j = 1;j + l -1 <= n;j++){
            cout<<ans[j][id[que[i]]]<<" ";
        }
        cout<<'\n';
    }
}  


//! MI SE SPIEEEEE!

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