Submission #908662

#	Time	Username	Problem	Language	Result	Execution time	Memory
908662		Dec0Dedd	Lottery (CEOI18_lot)	C++14	100 / 100	1649 ms	8588 KiB

lot

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 1e4+50;
const int Q = 110;

vector<pii> que;
vector<int> q2;
int n, l, q, ans[Q][N], a[N];

void add(int x, int df) {
    int ptr=lower_bound(que.begin(), que.end(), make_pair(df, -1))-que.begin();
    ++ans[ptr][x];
}

bool cmp(pii a, pii b) {
    return a.second < b.second;
}

void solve() {
    cin>>n>>l;
    for (int i=1; i<=n; ++i) cin>>a[i];

    cin>>q;
    for (int i=1; i<=q; ++i) {
        int k; cin>>k;
        que.push_back({k, i});
        q2.push_back(k);
    } sort(que.begin(), que.end());

    for (int d=1; d+l<=n; ++d) {
        // [1, l] and [d+1, d+l]

        int df=0;
        for (int r=0; r<l; ++r) {
            if (a[r+1] != a[d+1+r]) ++df;
        } add(1, df), add(d+1, df);

        //cout<<"FOR "<<1<<" - "<<d+1<<": "<<df<<"\n";
        int j=1;
        while (d+l+j <= n) {
            if (a[j] != a[d+j]) --df;
            if (a[l+j] != a[d+l+j]) ++df;
            add(1+j, df), add(d+1+j, df);
            //cout<<"FOR "<<1+j<<" - "<<d+1+j<<": "<<df<<"\n";
            ++j;
        }
    }

    for (int i=1; i<=q; ++i) {
        for (int j=0; j<N; ++j) ans[i][j]+=ans[i-1][j];
    }

    for (auto u : q2) {
        int x=lower_bound(que.begin(), que.end(), make_pair(u, -1))-que.begin();
        for (int i=1; i+l-1<=n; ++i) cout<<ans[x][i]<<" ";
        cout<<"\n";
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int t=1;
    while (t--) solve();
}

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