Submission #1161154

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161154		Ludissey	Lottery (CEOI18_lot)	C++20	100 / 100	538 ms	8288 KiB

lot

#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n,l,q; cin >> n >> l;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    cin >> q;
    vector<pair<int,int>> qrs(q);   
    vector<vector<int>> out(q,vector<int>(n,0));
    for (int i = 0; i < q; i++) { cin >> qrs[i].first; qrs[i].second=i; }

    sort(all(qrs));

    vector<pair<int,int>> cline(n);
    vector<int> cnt(l+1,0);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cline[j].second=(a[i]==a[j]);
            if(i>0&&j>0) cline[j].second+=cline[j-1].first;
            if(i>=l&&j>=l) cline[j].second-=(a[i-l]==a[j-l]);
        }
        for (int j = 0; j < n; j++) swap(cline[j].first,cline[j].second);
        if(i>=l-1){
            for (int j = l-1; j < n; j++) cnt[cline[j].first]++;
            int csum=-1;
            int k=0;
            for (int j = 0; j <= l; j++) {
                while(j>qrs[k].first&&k<sz(qrs)) {
                    out[qrs[k].second][i-l+1]=csum;
                    k++;
                }
                csum+=cnt[l-j];
            }
            while(l>=(l-qrs[k].first)&&k<sz(qrs)) {
                out[qrs[k].second][i-l+1]=csum;
                k++;
            }
            for (int j = 0; j < n; j++) cnt[cline[j].first]=0;
        }
    }
    for (int i = 0; i < q; i++)
    {
        for (int j = 0; j < n-l+1; j++)
        {
            cout << out[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