제출 #134739

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
134739		miguel	Lottery (CEOI18_lot)	C++14	0 / 100	1012 ms	552 KiB

lot

#include<bits/stdc++.h>
using namespace std;
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define sz size()
#define x first
#define y second
#define pi pair <int, int>
#define pii pair <int, pi>
#define vi vector <int>
const ll mod = 998244353;
int n, a[10001], q, l, idx[10001], ans[101][10002], miss[10003];
pi qry[1001];

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin>>n>>l;
    for(int i=1; i<=n; i++) cin>>a[i];
    cin>>q;
    for(int i=1; i<=q; i++){
        cin>>qry[i].x;
        qry[i].y=i;
    }
    sort(qry+1, qry+q+1);
    for(int xd=0; xd<=n+1; xd++){
        for(int i=1; i<=q; i++){
            if(qry[i].x<=xd) idx[xd]=i;
        }
    }
    for(int sh=1; sh<=n-l; sh++){
        fill(miss, miss+n+1, 0);
        //for(int i=1; i<=n; i++) cout<<miss[i];
        for(int i=1; i+sh<=n; i++){
            if(a[i]!=a[i+sh]){
                miss[i]++;
                miss[(min(n+2, i+l))]--;
            }
        }
        for(int i=1; i<=n; i++){
            miss[i]+=miss[i-1];
        }
        //if(sh==1){for(int i=1; i<=n; i++) cout<<miss[i]<<" "; cout<<endl;}
        for(int i=l; i<=n-sh; i++){
            ans[idx[miss[i]]][i-l+1]++;
            ans[idx[miss[i]]][i-l+1+sh]++;
        }
    }
    for(int i=1; i<=q; i++){
        for(int id=1; id<=n; id++) ans[i][id]+=ans[i-1][id];
    }
    for(int i=1; i<=q; i++){
        for(int id=1; id<=q; id++){
            if(qry[id].y==i){
                for(int xd=1; xd<=n-l+1; xd++) cout<<ans[id][xd]<<" ";
                cout<<"\n";
            }
        }
    }
}

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