Submission #134119

#	Time	Username	Problem	Language	Result	Execution time	Memory
134119		SamAnd	Lottery (CEOI18_lot)	C++17	100 / 100	1973 ms	12448 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 u[Q][N];
int ans[Q][N];
int hh[Q];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    scanf("%d", &q);
    for (int i = 1; i <= q; ++i)
    {
        b[i].i = i;
        scanf("%d", &b[i].d);
    }
    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;
            u[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] + u[i][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)
            printf("%d ", ans[hh[i]][j]);
        printf("\n");
    }
    return 0;
}

Compilation message (stderr)

lot.cpp: In function 'int main()':
lot.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
lot.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~
lot.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
lot.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &b[i].d);
         ~~~~~^~~~~~~~~~~~~~~

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