Submission #538248

#	Time	Username	Problem	Language	Result	Execution time	Memory
538248		alextodoran	Lottery (CEOI18_lot)	C++17	45 / 100	1092 ms	43572 KiB

lot

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 10000;
const int Q_MAX = 100;
const int B = 2000;

int n, len;
int a[N_MAX + 2];
int q;
int k[Q_MAX + 2];

int qord[Q_MAX + 2];
int qid[N_MAX + 2];

short int sim[N_MAX + 2][B + 2];
int pref[N_MAX + 2][Q_MAX + 2];

void solve (int l, int r) {
    for (int x = 1; x <= n - len + 1; x++) {
        for (int y = 1; y <= r - l + 1; y++) {
            sim[x][y] = 0;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = l; j <= r + len - 1; j++) {
            if (a[i] != a[j]) {
                int x1 = i - len + 1, y1 = j - len + 1;
                int x2 = i, y2 = j;
                int out1 = max({0, 1 - x1, l - y1});
                int out2 = max({0, x2 - (n - len + 1), y2 - r});
                x1 += out1; y1 += out1;
                x2 -= out2; y2 -= out2;
                if (x1 > x2 || y1 > y2) {
                    continue;
                }
                sim[x1][y1 - l + 1]++;
                sim[x2 + 1][(y2 + 1) - l + 1]--;
            }
        }
    }
    for (int x = 1; x <= n - len + 1; x++) {
        for (int y = 1; y <= r - l + 1; y++) {
            sim[x][y] += sim[x - 1][y - 1];
            pref[x][qid[sim[x][y]]]++;
        }
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> len;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    cin >> q;
    for (int i = 1; i <= q; i++) {
        cin >> k[i];
        qord[i] = i;
    }
    sort(qord + 1, qord + q + 1, [&] (const int &i, const int &j) {
        return k[i] < k[j];
    });
    for (int s = len, i = q + 1; s >= 0; s--) {
        while (i > 1 && k[qord[i - 1]] >= s) {
            i--;
        }
        qid[s] = i;
    }

    for (int i = 1; (i - 1) * B + 1 <= n - len + 1; i++) {
        solve((i - 1) * B + 1, min(i * B, n - len + 1));
    }
    for (int x = 1; x <= n - len + 1; x++) {
        for (int i = 1; i <= q; i++) {
            pref[x][i] += pref[x][i - 1];
        }
    }

    for (int i = 1; i <= q; i++) {
        for (int x = 1; x <= n - len + 1; x++) {
            cout << pref[x][qid[k[i]]] - 1 << " ";
        }
        cout << "\n";
    }

    return 0;
}

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