Submission #736533

#	Time	Username	Problem	Language	Result	Execution time	Memory
736533		study	Lottery (CEOI18_lot)	C++17	100 / 100	471 ms	12312 KiB

lot

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

const int N = 1e4+1, Q = 1e2+1;

int a[N],id[N];
int diff[N], ans[N][Q], res[N][Q];
pair<int,int> queries[N];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,l;
    cin >> n >> l;
    for (int i=0; i<n; ++i){
        cin >> a[i];
    }
    int q;
    cin >> q;
    for (int i=0; i<q; ++i){
        cin >> queries[i].first;
        queries[i].second = i;
    }
    sort(queries,queries+q);
    int idx = 0;
    for (int i=0; i<=n; ++i){
        while (idx < q and queries[idx].first < i) idx++;
        id[i] = idx;
    }
    for (int i=1; i<n-l+1; ++i){
        for (int j=0; j<l; ++j){
            if (a[i+j] != a[j]) diff[i]++;
        }
        ans[0][id[diff[i]]]++;
        ans[i][id[diff[i]]]++;
    }
    for (int i=1; i<n-l+1; ++i){
        for (int j=n-l; j>=i+1; --j){
            diff[j] = diff[j-1]-(a[i-1] != a[j-1])+(a[i+l-1] != a[j+l-1]);
            ans[i][id[diff[j]]]++;
            ans[j][id[diff[j]]]++;
        }
    }
    for (int i=0; i<n; ++i){
        res[i][queries[0].second] = ans[i][0];
        for (int j=1; j<q; ++j){
            ans[i][j] += ans[i][j-1];
            res[i][queries[j].second] = ans[i][j];
        }
    }
    for (int j=0; j<q; ++j){
        for (int i=0; i<n-l+1; ++i) cout << res[i][j] << ' ';
        cout << '\n';
    }
	return 0;
}

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