Submission #1222822

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222822		TsotneSV	Lottery (CEOI18_lot)	C++20	100 / 100	219 ms	12600 KiB

lot

#include <bits/stdc++.h>
using namespace std;
/*⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⠀⠀⠀⠀⠀⠀⠀⡄⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⣿⠛⣿⠀⠀⠀⠀⣤⣿⢻⡇⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⣿⡛⠀⣤⣿⣿⣤⣤⣿⣿⣤⢸⡇⠀
⠀⠀⠀⠀⠀⠀⠀⠀⣴⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠀
⠀⠀⠀⠀⠀⠀⠀⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡗⠀
⢠⣼⣿⣿⣿⣿⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷
⢸⣿⣿⡟⠛⠛⢿⣿⣿⣿⣿⣿⣿⣿⣤⣤⣤⣿⣿⣿⣿⣤⣤⣼⣿⣿
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠛⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⠋       
*/
#define fi first
#define se second
#define pb push_back
#define ins insert
#define sz(a) (int)(a.size())
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}

#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#include "debug.h"
#else
#define debug(...)
#endif

//const int mod = 1e9+7;
//const int mod = 998244353;
const int MAXN=1e4+5,MAXQ=105; 
const ll inf=1e9,INF=1e18; 

int n,l,q,A[MAXN],sum[MAXN][MAXQ]={0},minQ[MAXN],ans[MAXN][MAXQ];

void solve(int tc = 0){
    cin>>n>>l;

    for(int i=1;i<=n;i++) cin>>A[i];

    cin>>q; pii queries[q + 1];

    for(int i=1;i<=q;i++) cin>>queries[i].fi,queries[i].se = i;

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

    int idx = 1;

    for(int i=1;i<=n;i++) {
        while(idx <= q and queries[idx].fi < i) idx++;
        minQ[i] = idx;
    }

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

        int la = 1,ra = l,lb = diff+1,rb = diff+l,d = 0;

        for(int i=1;i<=l;i++) d += (A[la+i-1] != A[lb+i-1]);

        sum[la][minQ[d]]++; sum[lb][minQ[d]]++;

        while(rb < n) {
            d -= A[la] != A[lb];
            la++; lb++; ra++; rb++;
            d += A[ra] != A[rb];
            sum[la][minQ[d]]++; sum[lb][minQ[d]]++;
        }

    }

    for(int i=1;i<=n;i++) {
        for(int j=1;j<=q;j++) {
            sum[i][j] += sum[i][j-1];
            ans[i][queries[j].se] = sum[i][j];
        }
    }

    for(int i=1;i<=q;i++) {
        for(int j=1;j<=n-l+1;j++) cout<<ans[j][i]<<' ';
        cout<<endl;
    }

}

signed main(){

    ios_base::sync_with_stdio(false); cin.tie(0);

    int tc=1;
    //cin>>tc;
    for(int t = 0; t < tc; t++) solve(t);
}

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