Submission #524792

#	Time	Username	Problem	Language	Result	Execution time	Memory
524792		Deepesson	Lottery (CEOI18_lot)	C++17	100 / 100	978 ms	10332 KiB

lot

#include <bits/stdc++.h>
#define MAX 11000
int ans[MAX][155];
int valores[155];
int difs=0;
int addval(int u){
    int l=0,r=difs-1;
    while(l<r){
        int m = (l+r)/2;
        if(valores[m]>=u){
            r=m;
        }else l=m+1;
    }
    return l;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int N,L;
    std::cin>>N>>L;
    int array[N];
    for(auto&x:array)std::cin>>x;
    int Q;
    std::cin>>Q;
    std::vector<int> vec;
    std::map<int,int> mapa;
    int cur=0;
    std::vector<int> v;v.push_back(0);v.push_back(1e9);
    for(int i=0;i!=Q;++i){
        int x;
        std::cin>>x;
        v.push_back(x);
        vec.push_back(x);
    }
    std::sort(v.begin(),v.end());
    for(auto&x:v){
        if(mapa.find(x)==mapa.end()){
            valores[cur]=x;
            mapa[x]=cur;
            ++cur;
            ++difs;
        }
    }

    for(int j=1;j!=N;++j){
        if(j+L>N)break;
        int count=0;
        int cur1=0,cur2=j;
        for(int i=0;i!=L;++i){
            count+=(array[cur1]!=array[cur2]);
            ++cur1;
            ++cur2;
        }
        assert(cur2<=N&&cur1<=N);
        {
            int k = addval(count);
            ans[cur1-L][k]++;
            ans[cur2-L][k]++;
        }
        while(cur2!=N){
            count-=(array[cur1-L]!=array[cur2-L]);
            count+=(array[cur1]!=array[cur2]);
            ++cur1;++cur2;
            {
                int k =  addval(count);
                ans[cur1-L][k]++;
                ans[cur2-L][k]++;
            }
        }
    }

    for(int i=0;i!=N;++i){
        int sum=0;
        for(int j=0;j!=104;++j){
            sum+=ans[i][j];
            ans[i][j]=sum;
        }
    }
    for(auto&x:vec){
        for(int i=0;i<N-L+1;++i){
            std::cout<<ans[i][mapa[x]]<<" ";
        }
        std::cout<<"\n";
    }
}

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