Submission #950193

#	Time	Username	Problem	Language	Result	Execution time	Memory
950193		berr	Lottery (CEOI18_lot)	C++17	100 / 100	761 ms	8660 KiB

lot

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


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

    int len, n; cin >> n >> len;
    vector<int> ar(n);

    for(auto &i: ar) cin >> i;

    int q; cin >> q;
    vector<array<int, 2>> qu(q);

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

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

    int sum=0;
    vector<vector<int>> a(n, vector<int>(q, 0));

    auto calc=[&](int pos){
        int l=0, r=pos;
        int ans=0, ind=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";

            while(ind<q-1 && ans>qu[ind][0]) ind++;
            while(ind>0 && ans <= qu[ind-1][0]) ind--;

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

        }
    };

    for(int i=1; i<n; i++){
        calc(i);
    }   
    vector<int> 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";
    }


}   

Compilation message (stderr)

lot.cpp: In function 'int main()':
lot.cpp:25:9: warning: unused variable 'sum' [-Wunused-variable]
   25 |     int sum=0;
      |         ^~~

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