Submission #123212

#	Time	Username	Problem	Language	Result	Execution time	Memory
123212		semiauto	Lottery (CEOI18_lot)	C++14	100 / 100	938 ms	12448 KiB

lot

#include <bits/stdc++.h>
using namespace std;
int n,l,i,j,k,m,d;
int mas[100001],fix[100001],where[100001],pre[10001][102],ans[101][10001];
pair <int,int> q[101];
int main() {
    cin>>n>>l;
    for (i=1;i<=n;i++)
        cin>>mas[i];
    cin>>m;
    for (i=1;i<=m;i++) {
        cin>>d;
        q[i]={d,i};
    }
    sort(q+1,q+m+1);
    for (i=m;i>0;i--)
        where[q[i].first]=i;
    for (i=10000;i>=0;i--)
        if (!where[i])
            where[i]=where[i+1];
    for (d=1;d<=(n-l);d++) {
        for (i=1;i<=n;i++) {
            fix[i]=fix[i-1];
            if (mas[i]==mas[i+d])
                fix[i]++;
        }
        for (i=1;(i+d)<=(n-l+1);i++) {
            pre[i][where[l-fix[i+l-1]+fix[i-1]]]++;
            pre[i+d][where[l-fix[i+l-1]+fix[i-1]]]++;
        }
    }
    for (i=1;i<=m;i++)
        for (j=1;j<=(n-l+1);j++) {
            ans[q[i].second][j]=pre[j][i];
            pre[j][i+1]+=pre[j][i];
        }
    for (i=1;i<=m;i++) {
        for (j=1;j<(n-l+1);j++)
            cout<<ans[i][j]<<" ";
        cout<<ans[i][n-l+1]<<endl;
    }


}

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