Submission #267034

#	Time	Username	Problem	Language	Result	Execution time	Memory
267034		stefantaga	Lottery (CEOI18_lot)	C++14	100 / 100	1370 ms	12464 KiB

lot

#include <bits/stdc++.h>

using namespace std;
int n,l,i,v[10005],nr,q,smen[10005][105],solutie[10005][105],j,numar,k,st,dr,mij,sol;
struct wow
{
    int poz,val;
}query[105];
map <int,int> m;
bool compare (wow a,wow b)
{
    return a.val<b.val;
}
void adauga (int numar,int loc,int spatiu)
{
    int st=1,dr=q,sol=0,mij;
    st=1;
            dr=q;
            sol=0;
            while (st<=dr)
            {
                mij=(st+dr)/2;
                if (query[mij].val<numar)
                {
                    sol=mij;
                    st=mij+1;
                }
                else
                {
                    dr=mij-1;
                }
            }
            smen[loc][sol+1]++;
            smen[loc+spatiu][sol+1]++;
}
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    #ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
    #endif // HOME
    cin>>n>>l;
    for (i=1;i<=n;i++)
    {
        cin>>v[i];
    }
    cin>>q;
    for (i=1;i<=q;i++)
    {
        cin>>query[i].val;
        query[i].poz=i;
    }
    sort (query+1,query+q+1,compare);
    for (i=1;i+l-1<n;i++)
    {
        numar=0;
        for (j=1;j<=l;j++)
        {
            if (v[j]!=v[j+i])
            {
                numar++;
            }
        }
        adauga(numar,1,i);
        for (j=2;j+i+l-1<=n;j++)
        {
            if (v[j-1]!=v[j+i-1])
            {
                numar--;
            }
            if (v[j+l-1]!=v[j+l+i-1])
            {
                numar++;
            }
            adauga(numar,j,i);
        }
    }
    for (i=1;i<=n-l+1;i++)
    {
        for (j=1;j<=q;j++)
        {
            smen[i][j]+=smen[i][j-1];
            solutie[i][query[j].poz]+=smen[i][j];
        }
    }
    for (j=1;j<=q;j++)
    {
        for (i=1;i<=n-l+1;i++)
        {
            cout<<solutie[i][j]<<" ";
        }
        cout<<'\n';
    }
    return 0;
}

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