Submission #598292

#	Time	Username	Problem	Language	Result	Execution time	Memory
598292		1bin	Lottery (CEOI18_lot)	C++14	100 / 100	1143 ms	8408 KiB

lot

#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 1e4 + 5;
int n, l, d, a[NMAX], q, x, qry[105], p[NMAX][105], ix;
vector<int> tmp;

void add(int i, int v){
    while(v > tmp[ix]) ix++;
    while(ix && tmp[ix - 1] >= v) ix--;
    p[i][ix]++;
    return;
}

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> l;
    for(int i = 0; i < n; i++) cin >> a[i];
    cin >> q;
    for(int i = 0; i < q; i++){
        cin >> qry[i]; tmp.emplace_back(qry[i]);
    }
    tmp.emplace_back(1e9);
    sort(all(tmp));
    tmp.erase(unique(all(tmp)), tmp.end());
    
    for(int d = 1; d + l - 1 < n; d++){
        int v = 0;
        for(int i = 0; i < l; i++)
            if(a[i] != a[i + d]) v++;
        add(0, v); add(d, v);
        for(int i = 1; i + l - 1 + d < n; i++){
            if(a[i - 1] != a[i - 1 + d]) v--;
            if(a[i + l - 1] != a[i + l - 1 + d]) v++;
            add(i,v); add(i + d, v);
        }
    }
    
    for(int i = 0; i + l - 1 < n; i++)
        for(int j = 1; j < (int) tmp.size(); j++) p[i][j] += p[i][j - 1];
    for(int j = 0; j < q; j++){
        for(int i = 0; i + l - 1 < n; i++) cout << p[i][lower_bound(all(tmp), qry[j]) - tmp.begin()] << ' ';
        cout << '\n';
    }
    return 0;
}

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