Submission #163772

#	Time	Username	Problem	Language	Result	Execution time	Memory
163772		Alexa2001	Lottery (CEOI18_lot)	C++17	100 / 100	735 ms	12484 KiB

lot

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 1e4 + 5, Qmax = 205;

int a[Nmax], match[Nmax], where[Qmax];
pair<int,int> mat[Qmax];

int n, q, l;
int ans[Nmax][Qmax];


void new_match(int x, int y, int mat)
{
    ans[x][match[mat]] ++;
    ans[y][match[mat]] ++;
}

void prec(int d)
{
    int i, dif = 0;

    for(i=1; i<=l; ++i)
        dif += (a[i] != a[d+i]);
    
    new_match(1, d+1, dif);

    for(i=l+1; i+d<=n; ++i)
    {
        dif += (a[i] != a[i+d]);
        dif -= (a[i-l] != a[i+d-l]);

        new_match(i-l+1, i+d-l+1, dif);
    }
}

int main()
{
   // freopen("input", "r", stdin);
    cin.sync_with_stdio(false); cin.tie(0);

    cin >> n >> l;
    int i, j;
    for(i=1; i<=n; ++i) cin >> a[i];

    cin >> q;
    for(i=1; i<=q; ++i) cin >> mat[i].first, mat[i].second = i;

    sort(mat+1, mat+q+1);

    for(i=0; i<=l; ++i) 
        match[i] = lower_bound(mat+1, mat+q+1, make_pair(i, 0)) - mat;
    
    for(i=1; i<=n-l; ++i) 
        prec(i);

    for(i=1; i<=n; ++i)
        for(j=1; j<=q; ++j)
            ans[i][j] += ans[i][j-1];

    for(i=1; i<=q; ++i) where[mat[i].second] = i;

    for(i=1; i<=q; ++i)
    {
        for(j=1; j<=n-l+1; ++j) cout << ans[j][where[i]] << ' ';
        cout << '\n';
    }
    
    return 0;
}

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