Submission #232286

#	Time	Username	Problem	Language	Result	Execution time	Memory
232286		nicolaalexandra	Lottery (CEOI18_lot)	C++14	100 / 100	1836 ms	12320 KiB

lot

#include <bits/stdc++.h>
#define DIM 10010
#define DIMQ 102
using namespace std;

int v[DIM],dp[DIM][DIMQ],sol[DIMQ][DIM];
pair <int,int> qry[DIMQ];
int n,l,i,j,len,q;

void add_query (int poz, int val){
    int st = 1, dr = q, sol = q+1;
    while (st <= dr){
        int mid = (st+dr)>>1;
        if (qry[mid].first >= val){
            sol = mid;
            dr = mid-1;
        } else st = mid+1;
    }

    dp[poz][sol]++;

}
int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>l;
    for (i=1;i<=n;i++)
        cin>>v[i];
    cin>>q;
    for (i=1;i<=q;i++){
        cin>>qry[i].first;
        qry[i].second = i;
    }
    sort (qry+1,qry+q+1);

    for (len=1;len<=n-l;len++){

        int sum = 0;
        for (i=1;i<=l;i++)
            if (v[i] != v[i+len])
                sum++;

        add_query (1,sum);
        add_query (1+len,sum);

        for (i=l+1;i+len<=n;i++){
            if (v[i] != v[i+len])
                sum++;
            if (v[i-l] != v[i+len - l])
                sum--;

            add_query (i-l+1,sum);
            add_query (i+len - l+1,sum);
        }
    }


    for (j=1;j<=n;j++){
        for (i=1;i<=q;i++){
            dp[j][i] += dp[j][i-1];
            sol[qry[i].second][j] = dp[j][i];
        }
    }

    for (i=1;i<=q;i++){
        for (j=1;j<=n-l+1;j++)
            cout<<sol[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