Submission #482848

#	Time	Username	Problem	Language	Result	Execution time	Memory
482848		Monarchuwu	Lottery (CEOI18_lot)	C++17	45 / 100	29 ms	13544 KiB

lot

#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef long long ll;
const int N = 2000 + 3, Q = 100 + 3, N3 = 1e4 + 3;
const ll base = 1e9 + 7, mod = 1e9 + 9;

int n, l;
int a[N];
int q, k[Q];

int dp[N][N];
void subtask2() {
    for (int dist = 1; dist <= n - l; ++dist) {
        int i(1), j(1 + dist), diff(0);
        for (int k = 0; k < l; ++k) diff += a[i + k] != a[j + k];

        for (; j <= n - l + 1; ++i, ++j) {
            ++dp[i][diff], ++dp[j][diff];
            diff -= a[i] != a[j];
            diff += a[i + l] != a[j + l];
        }
    }

    for (int i = 1; i <= n; ++i)
        for (int k = 1; k <= l; ++k) dp[i][k] += dp[i][k - 1];

    for (int i = 0; i < q; ++i)
        for (int j = 1; j <= n - l + 1; ++j) cout << dp[j][k[i]] << " \n"[j == n - l + 1];
}

ll h[N3], pw[N3];
int get(int l, int r) {
    return (h[r] - h[l - 1] * pw[r - l + 1] + mod * mod) % mod;
}
void subtask3() {
    pw[0] = 1;
    for (int i = 1; i <= n; ++i) {
        h[i] = (h[i - 1] * base + a[i]) % mod;
        pw[i] = pw[i - 1] * base % mod;
    }
    unordered_map<int, int> mp;
    for (int i = 1; i <= n - l + 1; ++i)
        ++mp[get(i, i + l - 1)];

    for (int i = 1; i <= n - l + 1; ++i)
        cout << mp[get(i, i + l - 1)] - 1 << " \n"[i == n - l + 1];
}

int ans[N3];
void subtask4() {
    for (int dist = 1; dist <= n - l; ++dist) {
        int i(1), j(1 + dist), diff(0);
        for (int k = 0; k < l; ++k) diff += a[i + k] != a[j + k];

        for (; j <= n - l + 1; ++i, ++j) {
            if (diff <= k[0]) ++ans[i], ++ans[j];
            diff -= a[i] != a[j];
            diff += a[i + l] != a[j + l];
        }
    }

    for (int i = 1; i <= n - l + 1; ++i)
        cout << ans[i] << " \n"[i == n - l + 1];
}

int tmp[Q], inv[N3];
int dp2[N3][Q];
void subtask5() {
    copy(k, k + q, tmp + 1);
    sort(tmp, tmp + q + 1);
    int cnt = unique(tmp, tmp + q + 1) - tmp;
    for (int i = 0; i < cnt; ++i)
        inv[tmp[i]] = i;

    for (int dist = 1; dist <= n - l; ++dist) {
        int i(1), j(1 + dist), diff(0), ptr(0);
        for (int k = 0; k < l; ++k) {
            diff += a[i + k] != a[j + k];
            if (diff > tmp[ptr]) ++ptr;
        }

        for (; j <= n - l + 1; ++i, ++j) {
            ++dp[i][ptr], ++dp[j][ptr];

            diff -= a[i] != a[j];
            if (diff < tmp[ptr]) --ptr;

            diff += a[i + l] != a[j + l];
            if (diff > tmp[ptr]) ++ptr;
        }
    }

    for (int i = 1; i <= n; ++i)
        for (int k = 1; k < cnt; ++k) dp[i][k] += dp[i][k - 1];

    for (int i = 0; i < q; ++i)
        for (int j = 1; j <= n - l + 1; ++j)
            cout << dp[j][inv[k[i]]] << " \n"[j == n - l + 1];
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> n >> l;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    cin >> q;
    for (int i = 0; i < q; ++i)
        cin >> k[i];

    if (n <= 2000) subtask2();
    else if (q == 1) {
        if (k[0] == 0) subtask3();
        else subtask4();
    }
    else subtask5();
}

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