Submission #482850

#	Time	Username	Problem	Language	Result	Execution time	Memory
482850		Monarchuwu	Lottery (CEOI18_lot)	C++17	0 / 100	607 ms	4380 KiB

lot

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

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

int tmp[Q], inv[N];
int dp[N][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];

    subtask5();
}

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