Submission #104954

#	Time	Username	Problem	Language	Result	Execution time	Memory
104954		eriksuenderhauf	Lottery (CEOI18_lot)	C++11	100 / 100	1034 ms	8284 KiB

lot

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define pii pair<int, int>
#define mp make_pair
#define se second
using namespace std;
const int MAXN = 1e4 + 5;
int a[MAXN], cnt[MAXN];
pii qry[101];
int ans[101][MAXN];
int ind[101];

int main()
{
    int n, l, q, k;
    scanf("%d %d", &n, &l);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        scanf("%d", &k);
        qry[i] = {k, i};
    }
    sort(qry, qry + q);
    for (int j = 1; j < n - l + 1; j++) {
        int diff = 0;
        for (int m = 0; m < l; m++)
            diff += a[m] != a[j + m];
        int st = lower_bound(qry, qry + q, mp(diff, 0)) - qry;
        ans[st][0]++, ans[st][j]++;
        for (int m = 1; j + l - 1 + m < n; m++) {
            diff -= a[m - 1] != a[j + m - 1];
            diff += a[l - 1 + m] != a[j + l - 1 + m];
            st = lower_bound(qry, qry + q, mp(diff, 0)) - qry;
            ans[st][m]++, ans[st][m + j]++;
        }
    }
    for (int i = 1; i < q; i++) {
        for (int j = 0; j < n; j++)
            ans[i][j] += ans[i - 1][j];
        ind[qry[i].se] = i;
    }
    for (int i = 0; i < q; i++) {
        for (int j = 0; j < n - l + 1; j++)
            printf("%d ", ans[ind[i]][j]);
        printf("\n");
    }
    return 0;
}

Compilation message (stderr)

lot.cpp: In function 'int main()':
lot.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &l);
     ~~~~~^~~~~~~~~~~~~~~~~
lot.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~
lot.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
lot.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &k);
         ~~~~~^~~~~~~~~~

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