Submission #524784

#	Time	Username	Problem	Language	Result	Execution time	Memory
524784		Deepesson	Lottery (CEOI18_lot)	C++17	0 / 100	337 ms	2408 KiB

lot

#include <bits/stdc++.h>
#define MAX 11000
short ans[MAX][105];
int valores[105];
int difs=0;
int addval(int u){
    int l=0,r=difs-1;
    while(l<r){
        int m = (l+r+1)/2;
        if(valores[m]<=u){
            l=m;
        }else r=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);
    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;
        }
    }
    valores[cur]=1e9;
    ++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){
            if(array[cur1]!=array[cur2])++count;
            ++cur1;
            ++cur2;
        }
        assert(cur2<=N&&cur1<=N);
        if(mapa.find(count)!=mapa.end()){
            int k = addval(count);
            ans[cur1-L][k]++;
            ans[cur2-L][k]++;
        }
        while(cur2!=N){
            count-=(array[cur1-L]!=array[cur2-L]);
        ///    printf("skipa %d %d (%d %d)\n",cur1-L,cur2-L,cur1,cur2);
            ++cur1;++cur2;
            count+=(array[cur1]!=array[cur2]);
           /// printf("diferenca %d (%d %d)\n",count,cur1,cur2);
            if(mapa.find(count)!=mapa.end()){
                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: 0 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20