Submission #223105

#	Time	Username	Problem	Language	Result	Execution time	Memory
223105		MKopchev	Lottery (CEOI18_lot)	C++14	100 / 100	1150 ms	8440 KiB

lot

#include<bits/stdc++.h>
using namespace std;
const int nmax=1e4+42,qmax=1e2+5;

int n,l;
int inp[nmax];

pair<int/*k*/,int/*id*/> queries[nmax];

int where_begins[nmax];

int pref[nmax];

int output[qmax][nmax];

int original[nmax];
int q;

int main()
{
    scanf("%i%i",&n,&l);

    for(int i=1;i<=n;i++)scanf("%i",&inp[i]);

    scanf("%i",&q);
    for(int i=1;i<=q;i++)
    {
        scanf("%i",&queries[i].first);
        queries[i].second=i;

        original[i]=queries[i].first;
    }

    sort(queries+1,queries+q+1);

    for(int i=1;i<=n;i++)
        where_begins[i]=lower_bound(queries+1,queries+q+1,make_pair(i,0))-queries;

    for(int diff=1;diff<=n;diff++)
    {
        for(int i=1;i<=n;i++)pref[i]=0;

        for(int s=1;s+diff<=n;s++)
        {
            int t=s+diff;

            if(inp[s]==inp[t])continue;

            //common of [0, l-1], [-inf, s-1], [t-n+l-1,+inf]
            int i_low=max(0,t-n+l-1),i_high=min(s-1,l-1);

            //all [s-i, t-i] for i_low<=i<=i_high gain 1

            pref[s-i_high]++;
            pref[s-i_low+1]--;

            //cout<<s<<" "<<t<<" "<<i_low<<" "<<i_high<<endl;
        }

        for(int i=1;i<=n-l+1;i++)
            pref[i]=pref[i]+pref[i-1];

        for(int s=1;s+diff<=n-l+1;s++)
        {
            int t=s+diff;
            //difference between s and t is pref[s]

            int current=pref[s];

            //cout<<"distance between "<<s<<" and "<<t<<" is "<<current<<endl;

            output[where_begins[current]][s]++;
            output[where_begins[current]][t]++;
        }
    }

    for(int i=1;i<=q;i++)
        for(int j=1;j<=n;j++)
            output[i][j]+=output[i-1][j];

    for(int i=1;i<=q;i++)
    {
        for(int j=1;j<=n-l+1;j++)
        {
            if(j!=1)printf(" ");
            printf("%i",output[where_begins[original[i]]][j]);
        }
        printf("\n");
    }

    return 0;
}

Compilation message (stderr)

lot.cpp: In function 'int main()':
lot.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i",&n,&l);
     ~~~~~^~~~~~~~~~~~~~
lot.cpp:23:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=n;i++)scanf("%i",&inp[i]);
                          ~~~~~^~~~~~~~~~~~~~
lot.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&q);
     ~~~~~^~~~~~~~~
lot.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&queries[i].first);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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