Submission #1254577

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254577		chikien2009	Lottery (CEOI18_lot)	C++20	100 / 100	679 ms	8308 KiB

lot

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int n, m, q, l, a[10000], num[100][10000], pre[10000], b[100], c[100], d;

int main()
{
    setup();

    cin >> n >> l;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }
    cin >> q;
    for (int i = 0; i < q; ++i)
    {
        cin >> b[i];
        c[i] = b[i];
    }
    sort(c, c + q);
    m = unique(c, c + q) - c;
    for (int i = 1; i < n; ++i)
    {
        fill_n(pre, n, 0);
        for (int j = 0, k = i; k < n; ++k, ++j)
        {
            pre[k] = pre[k - 1] + (a[j] != a[k]);
            if (l - 1 <= j)
            {
                d = lower_bound(c, c + m, pre[k] - pre[k - l]) - c;
                if (d < m)
                {
                    num[d][k - l + 1]++;
                    num[d][j - l + 1]++;
                }
            }
        }
    }
    for (int i = 1; i < m; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            num[i][j] += num[i - 1][j];
        }
    }
    for (int i = 0; i < q; ++i)
    {
        b[i] = lower_bound(c, c + m, b[i]) - c;
        for (int j = 0; j < n - l + 1; ++j)
        {
            cout << num[b[i]][j] << " ";
        }
        cout << "\n";
    }
    return 0;
}

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