Submission #134125

#	Time	Username	Problem	Language	Result	Execution time	Memory
134125		SamAnd	Lottery (CEOI18_lot)	C++17	100 / 100	1951 ms	8416 KiB

lot

#include <bits/stdc++.h>
using namespace std;
const int N = 10004, Q = 102;
struct ban
{
    int i;
    int d;
};
bool operator<(const ban& a, const ban& b)
{
    return a.d < b.d;
}

int n, m;
int a[N];
int q;
ban b[N];

int t[N];

int p[N];
int np[N];

int ans[Q][N];
int hh[Q];

int ka()
{
    int x = 0;
    while (1)
    {
        char y = getchar();
        if (y == ' ' || y == '\n')
            return x;
        x = (x * 10) + (y - '0');
    }
}

char e[10];
void tp(int x)
{
    if (x == 0)
    {
        putchar('0');
        putchar(' ');
        return;
    }
    int i = 0;
    while (x)
    {
        e[i++] = (x % 10) + '0';
        x /= 10;
    }
    for (i = i - 1; i >= 0; --i)
        putchar(e[i]);
    putchar(' ');
}

int main()
{
    n = ka();
    m = ka();
    for (int i = 1; i <= n; ++i)
        a[i] = ka();
    q = ka();
    for (int i = 1; i <= q; ++i)
    {
        b[i].i = i;
        b[i].d = ka();
    }
    sort(b + 1, b + q + 1);
    for (int d = 0; d <= m; ++d)
    {
        int l = 1, r = q;
        while ((r - l) > 4)
        {
            int m = (l + r) / 2;
            if (b[m].d >= d)
                r = m;
            else
                l = m;
        }
        bool z = false;
        for (int m = l; m <= r; ++m)
        {
            if (b[m].d >= d)
            {
                t[d] = m;
                z = true;
                break;
            }
        }
        if (!z)
            t[d] = q + 1;
    }
    for (int i = 1; i <= n; ++i)
    {
        memset(np, 0, sizeof np);
        for (int j = 1; j <= n; ++j)
        {
            np[j] = p[j - 1];
            if (a[i] != a[j])
                ++np[j];
            if (i - m >= 1 && j - m >= 1)
            {
                if (a[i - m] != a[j - m])
                    --np[j];
            }
        }
        memcpy(p, np, sizeof np);
        for (int j = m; j <= n; ++j)
        {
            if (i == j)
                continue;
            ans[t[p[j]]][i]++;
            /*for (int k = 1; k <= q; ++k)
            {
                if (p[j] <= b[k].d)
                    ans[b[k].i][i]++;
            }*/
        }
    }
    for (int j = m; j <= n; ++j)
    {
        for (int i = 1; i <= q; ++i)
            ans[i][j] += ans[i - 1][j];
    }
    for (int i = 1; i <= q; ++i)
        hh[b[i].i] = i;
    for (int i = 1; i <= q; ++i)
    {
        for (int j = m; j <= n; ++j)
            tp(ans[hh[i]][j]);
        putchar('\n');
    }
    return 0;
}

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