Submission #1162489

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162489		simona1230	Lottery (CEOI18_lot)	C++20	45 / 100	156 ms	131072 KiB

lot

#include <bits/stdc++.h>
using namespace std;
int n,l;
int a[200001];
int q,k[200001];

void read()
{
    cin>>n>>l;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    cin>>q;
    for(int i=1;i<=q;i++)
        cin>>k[i];
}

map<int,vector<int> > id;
struct itv
{
    int l,r,v;
    itv(){}
    itv(int _l,int _r,int _v)
    {
        l=_l;
        r=_r;
        v=_v;
    }
};
vector<itv> v;
int d[2001][2001];
int act[2001];
vector<int> rem[2001];

bool cmp(itv i1,itv i2)
{
    return i1.r<i2.r;
}

bool cmp2(itv i1,itv i2)
{
    return i1.v<i2.v;
}

int ans[2001][2001];

void prec()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<id[a[i]].size();j++)
        {
            int li=id[a[i]][j];
            //cout<<li-l+1<<" "<<li<<endl;
            v.push_back({max(1,li-l+1),li,i-li});
        }

        id[a[i]].push_back(i);
    }

    sort(v.begin(),v.end(),cmp);

    int j=0;
    for(int i=1;i<=n;i++)
    {
        while(j<v.size()&&v[j].l<=i)
        {
            act[v[j].v]++;
            rem[v[j].r].push_back(v[j].v);
            j++;
        }

        //cout<<i<<": ";
        for(int x=1;x<=n;x++)
        {
            //cout<<act[x]<<" ";
            if(act[x])d[i][i+x]-=act[x];
        }
        //cout<<endl;

        for(int x=0;x<rem[i].size();x++)
        {
            act[rem[i][x]]--;
        }
    }

    for(int i=1;i<=n-l+1;i++)
    {
        for(int x=i+1;x<=n-l+1;x++)
        {
            d[i][x]+=l;
            ans[i][d[i][x]]++;
            ans[x][d[i][x]]++;

            //cout<<i<<" "<<x<<" "<<d[i][x]<<endl;
        }
    }

    for(int i=0;i<=l;i++)
    {
        for(int x=1;x<=n;x++)
        {
            ans[x][i]+=ans[x][i-1];
        }
    }

    for(int i=1;i<=q;i++)
    {
        for(int x=1;x<=n-l+1;x++)
            cout<<ans[x][k[i]]<<" ";
        cout<<endl;
    }

}

int main()
{
    read();
    prec();
    return 0;
}

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