Submission #897836

#	Time	Username	Problem	Language	Result	Execution time	Memory
897836		alexdd	Lottery (CEOI18_lot)	C++17	100 / 100	644 ms	8240 KiB

lot

#include<bits/stdc++.h>
using namespace std;
int n,lun,cntq;
int a[10005];
int cntd[10005];
vector<pair<int,int>> qrys;
int unde[105];
int rez[105][10005];
int ultima[10005];
void solve()
{
    for(int i=0;i<=n;i++)
    {
        ultima[i]=cntq;
        for(int j=cntq-1;j>=0;j--)
            if(i <= qrys[j].first && (j==0 || i > qrys[j-1].first))
                ultima[i] = j;
    }
    for(int dif=-n;dif<=n;dif++)
    {
        if(dif==0)
            continue;

        int idk=0;
        for(int i=max(1,-dif+1);i<=min(n,n-dif);i++)
        {
            if(a[i]!=a[i+dif])
                idk++;
            cntd[i] = idk;
        }
        for(int i=max(1,-dif+1);i<=min(n-lun+1,n-dif-lun+1);i++)
        {
            rez[ultima[cntd[i+lun-1] - cntd[i-1]]][i]++;
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<cntq;j++)
            rez[j][i] += rez[j-1][i];

}
signed main()
{
    cin>>n>>lun;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    cin>>cntq;
    qrys.resize(cntq);
    for(int i=0;i<cntq;i++)
    {
        cin>>qrys[i].first;
        qrys[i].second = i;
    }
    sort(qrys.begin(),qrys.end());
    for(int i=0;i<cntq;i++)
        unde[qrys[i].second] = i;
    solve();
    for(int i=0;i<cntq;i++)
    {
        for(int j=1;j+lun-1<=n;j++)
            cout<<rez[unde[i]][j]<<" ";
        cout<<"\n";
    }
    return 0;
}
/**

cntd[dif][poz] = numarul de mismatches a[x] != a[x+dif], unde x = 1..poz
cntc[dif][i] = cntd[dif][i+lun-1] - cntd[dif][i-1] = distanta de la intervalul i..i+lun-1 la i+dif..i+dif+lun-1 este

distanta de la intervalul i..i+lun-1 la i+dif..i+dif+lun-1 este:
cntd[dif][i+lun-1] - cntd[dif][i-1]

ne fixam dif
vedem cum influenteaza dif cele q queryuri

*/

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