oj.uz

Submission #223104

# Submission time Handle Problem Language Result Execution time Memory
223104 2020-04-14T18:50:16 Z MKopchev Lottery (CEOI18_lot) C++14
0 / 100
 993 ms 588 KB 
#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]--;

        }

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

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

            int current=pref[s];

            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]-1);
        }
        printf("\n");
    }

    return 0;
}

Compilation message

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
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 993 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 993 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -