Submission #1152019

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152019		trufanov.p	Lottery (CEOI18_lot)	C++20	100 / 100	537 ms	12468 KiB

lot

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <string>
#include <queue>
#include <unordered_set>
#include <deque>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, l;
    cin >> n >> l;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    vector<pair<int, int>> qr;
    int q;
    cin >> q;
    for (int i = 0; i < q; ++i) {
        int k;
        cin >> k;
        qr.push_back({ k, i });
    }
    sort(qr.begin(), qr.end());
    vector<vector<int>> add(n, vector<int>(q));
    vector<int> suff(l + 1);
    int itd = 0, its = 0;
    while (itd <= l || its < q) {
        if (itd == l + 1) {
            break;
        }
        if (its == q) {
            suff[itd] = q;
            itd++;
            continue;
        }
        if (itd > qr[its].first) {
            its++;
        } else {
            suff[itd] = its;
            itd++;
        }
    }
    for (int shift = 1; shift + l <= n; ++shift) {
        int curdiff = 0;
        for (int i = 0; i < l; ++i) {
            if (a[i] != a[i + shift]) {
                curdiff++;
            }
        }
        if (suff[curdiff] < q) {
            add[0][suff[curdiff]]++;
            add[shift][suff[curdiff]]++;
        }
        for (int i = 1; i + shift + l <= n; ++i) {
            if (a[i - 1] != a[i + shift - 1]) {
                curdiff--;
            }
            if (a[i + l - 1] != a[i + shift + l - 1]) {
                curdiff++;
            }
            if (suff[curdiff] < q) {
                add[i][suff[curdiff]]++;
                add[i + shift][suff[curdiff]]++;
            }
        }
    }
    vector<vector<int>> ans(q, vector<int>(n));
    for (int i = 0; i + l <= n; ++i) {
        int curs = 0;
        for (int j = 0; j < q; ++j) {
            curs += add[i][j];
            ans[qr[j].second][i] = curs;
        }
    }
    for (int i = 0; i < q; ++i) {
        for (int j = 0; j + l <= n; ++j) {
            cout << ans[i][j] << ' ';
        }
        cout << '\n';
    }
}

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