Submission #825050

#	Time	Username	Problem	Language	Result	Execution time	Memory
825050		zsombor	Lottery (CEOI18_lot)	C++17	100 / 100	1807 ms	8268 KiB

lot

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, l, q, k, L, R, M, b;
vector <int> a(1e4, 0);
vector <int> v(1e4 + 1, 0);
vector <pair<int, int>> Q;
vector <vector<int>> ans(101, vector <int>(1e4 + 1));
vector <int> nw(101);

int bin(int val) {
    L = -1, R = q;
    while (R - L > 1) {
        M = (L + R) / 2;
        (Q[M].first < val ? L = M : R = M);
    }
    return R;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> l;
    for (int i = 0; i < n; i++) cin >> a[i];
    cin >> q;
    Q.resize(q);
    for (int i = 0; i < q; i++) {
        cin >> Q[i].first;
        Q[i].second = i;
    }
    sort(Q.begin(), Q.end());
    for (int i = 1; i <= n - l; i++) {
        for (int j = 0; j < n - i; j++) {
            if (a[j] != a[j + i]) continue;
            L = max(0, j - l + 1), R = min(j + i, n - l);
            R -= i;
            if (L > R) continue;
            v[R]++;
            if (L) v[L - 1]--;
        }
        for (int j = n - l - i; j >= 0; j--) {
            v[j] += v[j + 1];
            v[j + 1] = 0;
            b = bin(l - v[j]);
            ans[b][j]++;
            ans[b][j + i]++;
        }
        v[0] = 0;
    }
    for (int i = 1; i < q; i++) {
        for (int j = 0; j < n; j++) {
            ans[i][j] += ans[i - 1][j];
        }
    }
    for (int i = 0; i < q; i++) nw[Q[i].second] = i;
    for (int i = 0; i < q; i++) {
        for (int j = 0; j <= n - l; j++) {
            cout << ans[nw[i]][j] << " ";
        }
        cout << "\n";
    }
}

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