제출 #1286268

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286268		domi	Lottery (CEOI18_lot)	C++20	100 / 100	831 ms	20188 KiB

lot

#include <bits/stdc++.h>

#define int long long
#define fi first
#define se second

#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))
#define vi vector<int>
#define YES { cout << "YES" << endl; return; }
#define NO { cout << "NO" << endl; return; }

using ll = long long;
using pii = std::pair<int, int>;

const int NMAX = 1e4;
const int QMAX = 2e2;

using namespace std;

vector<pii>qs;
int a[NMAX + 5], match[NMAX + 5], ans[QMAX + 5][NMAX + 5], out[QMAX + 5][NMAX + 5], n, l, q;

signed main() {
    cin >> n >> l;

    for(int i = 1; i <= n; ++i)
        cin >> a[i];

    cin >> q;
    qs.resize(q);
    for (int i = 0; i < q; ++i) {
        cin >> qs[i].fi;
        qs[i].se = i;
    }
    sort(all(qs));

    for (int d = 1; d + l <= n; ++d) {
        fill(match + 1, match + n + 1, 0LL);

        for (int i = 1; i + d <= n; ++i)
            match[i] = match[i - 1] + (a[i] != a[i + d]);

        for (int i = 1; i + l - 1 <= n && i + d + l - 1 <= n; ++i) {
            int j = i + d;
            int dist = match[i + l - 1] - match[i - 1];
            int pos = lower_bound(all(qs), make_pair(dist, -1LL)) - qs.begin();
            if (pos < q) {
                ++ans[pos][i - 1];
                ++ans[pos][j - 1];
            }
         }
    }

    for (int k = 1; k < q; ++k) {
        for (int i = 0; i < n - l + 1; ++i)
            ans[k][i] += ans[k - 1][i];
    }

    for (int k = 0; k < q; ++k) {
        for (int i = 0; i < n - l + 1; ++i)
             out[qs[k].second][i] = ans[k][i];
    }

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

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