제출 #232252

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
232252		nicolaalexandra	Lottery (CEOI18_lot)	C++14	0 / 100	535 ms	4456 KiB

lot

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

int v[DIM],dp[DIM][DIMQ],sol[DIMQ][DIM],f[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])
                f[i] = 1, sum++;
            else f[i] = 0;
        }

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

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

            if (f[i-1]) /// ala pe care il scot
                sum--;

            add_query (i,sum);
            add_query (i+len,sum);
        }

    }


    for (j=1;j<=n-l+1;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: 0 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20