Submission #950216

#	Time	Username	Problem	Language	Result	Execution time	Memory
950216		berr	Lottery (CEOI18_lot)	C++17	100 / 100	438 ms	6292 KiB

lot

#include <bits/stdc++.h>
using namespace std;
vector<int> ar;
vector<array<int, 2>> qu;

int n, len, q;
short a[(int)1e4][101];
short ind[(int)1e4+1];

void calc(int pos){
    short l=0, r=pos;
    short ans=0;
    if(pos+l-1>=n) return;

    for(int j=0; j+pos<n; j++){
        if(ar[j]!=ar[j+pos]) ans++;
        if(j-len>=0){
            ans-=(ar[j-len]!=ar[j-len+pos]);
        }   
      //  cout<<ans<<"\n";

    
        if(j>=len-1){
            if(ind[ans]==q){
                l++; r++;
                continue;
            }
            a[l][ind[ans]]++;
            a[r][ind[ans]]++;
            l++; r++;
        }

    }
};


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

    cin >> n >> len;
    ar.resize(n);
    
    for(auto &i: ar) cin >> i;

    cin >> q;
    qu.resize(q);

    for(int i=0; i<q; i++){
        cin >> qu[i][0];
        qu[i][1] = i;
    }

    sort(qu.begin(), qu.end());

    int p=0;
    for(int j=0; j<=n; j++){
        while(p<q&&qu[p][0]< j) p++;
        ind[j]=p;
    }
    
    for(int i=1; i<n; i++){
        calc(i);
    }   
    vector<short> pos(q);

    for(int i=0; i<q; i++){
        pos[qu[i][1]]=i;
    }

    for(int i=0; i<n; i++){
        for(int j=1; j<q; j++){
            a[i][j] += a[i][j-1];
        }

    }
    for(int j=0; j<q; j++){
        for(int i=0; i+len-1<n; i++){
            cout<<a[i][pos[j]]<<" ";
        }
        cout<<"\n";
    }


}   

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