Submission #1291453

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291453		nguyenkhangninh99	Lottery (CEOI18_lot)	C++20	100 / 100	253 ms	12492 KiB

lot

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int maxn = 1e4 + 5, maxq = 1e2 + 5;
int a[maxn], cnt[maxn][maxq], nxt[maxn], qry[maxq], tmp[maxq], pos[maxn];
void solve(){
    int n, l; cin >> n >> l;
    for(int i = 1; i <= n; i++) cin >> a[i];
    int q; cin >> q;
    for(int i = 1; i <= q; i++){
        cin >> qry[i];
        tmp[i] = qry[i];
    }
    sort(tmp + 1, tmp + q + 1);
    tmp[q + 1] = l;

    int cur = 1;
    for(int i = 0; i <= l; i++){
        while(tmp[cur] < i) cur++;
        nxt[i] = cur;//vị trí trong mảng sau nén
    }

    for(int i = 2; i + l - 1 <= n; i++){
        int diff = 0;
        for(int j = i; j <= i + l - 1; j++) diff += (a[j - i + 1] != a[j]);
        cnt[1][nxt[diff]]++;
        cnt[i][nxt[diff]]++;
        int j = 1, k = i;
        while(k + l <= n){
            diff -= (a[j] != a[k]);
            diff += (a[j + l] != a[k + l]);
            j++; 
            k++;
            cnt[j][nxt[diff]]++;
            cnt[k][nxt[diff]]++;
        }
    }

    for(int i = 1; i <= q; i++) pos[tmp[i]] = i;
    for(int i = 1; i <= q; i++) for(int j = 1; j <= n - l + 1; j++) cnt[j][i] += cnt[j][i - 1];

    for(int i = 1; i <= q; i++){
        for(int j = 1; j <= n - l + 1; j++) cout << cnt[j][pos[qry[i]]] << ' ';
        cout << "\n";
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    solve();
    return 0;
}

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