Submission #307538

#	Time	Username	Problem	Language	Result	Execution time	Memory
307538		wildturtle	Lottery (CEOI18_lot)	C++14	100 / 100	1167 ms	12408 KiB

lot

#include<bits/stdc++.h>
using namespace std;
int a,n,l,A[10004],C[10004],D[10004][102],ans[10004][102],t,r,st[10004];
pair <int,int> B[10004];
int main() {
    cin>>n>>l;
    for(int i=1;i<=n;i++) {
        cin>>A[i];
    }
    cin>>t;
    for(int i=1;i<=t;i++) {
        cin>>B[i].first;
        B[i].second=i;
    }
    sort(B+1,B+1+t);
    /*for(int i=1;i<=t;i++) {
        st.insert({B[i].first,i});
    }*/
    for(int i=0;i<=n;i++) {
        while(B[r].first<i && r<=t) r++;
        st[i]=r;
    }
    for(int d=1;d<=n-l;d++) {
        for(long long i=1;i<=n;i++)
        C[i]=0;
        for(int i=1;i<=n-d;i++) {
            r=i+d;
            if(A[i]!=A[r]) { C[i]=1; }
        }
        for(long long i=1;i<=n;i++) {
            //cout<<C[i]<<" ";
            C[i]+=C[i-1];
        }
        //cout<<endl;
        for(long long i=1;i+d+l-1<=n;i++) {
            r=i+l-1;
            a=C[r]-C[i-1];
            //cout<<a<<"-";
            /*it=st.upper_bound({a,-1});
            if(it==st.end()) { cout<<"*"; continue; }*/
            //cout<<(*it).second<<" ";
            D[i][st[a]]++;
            D[i+d][st[a]]++;
        }
        //cout<<endl;
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=t;j++) {
            D[i][j]+=D[i][j-1];
        }
    }
    for(int i=1;i<=t;i++) {
        for(int j=1;j<=n;j++) {
            ans[j][B[i].second]=D[j][i];
        }
    }
    for(int i=1;i<=t;i++) {
        for(int j=1;j<=n-l+1;j++) {
            cout<<ans[j][i]<<" ";
        }
        cout<<endl;
    }
}

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