Submission #557635

#	Time	Username	Problem	Language	Result	Execution time	Memory
557635		Vladth11	Lottery (CEOI18_lot)	C++14	35 / 100	504 ms	588 KiB

lot

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <long double, pii> muchie;

const ll NMAX = 10002;
const ll VMAX = 1001;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 447;
const ll base = 31;
const ll nr_of_bits = 15;

int v[NMAX];
int f[NMAX];
pii q[NMAX];
int sol[101][NMAX];
int ans[101][NMAX];

void update(int x, int y){
    if(f[y] != 0){
        sol[f[y]][x]++;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int i, n, l, qq;
    cin >> n >> l;
    for(i = 1; i <= n; i++){
        cin >> v[i];
    }
    cin >> qq;
    for(i = 1; i <= qq; i++){
        int x;
        cin >> x;
        q[i] = {x, i};
    }
    sort(q + 1, q + qq + 1);
    for(i = 1; i <= qq; i++){
        f[q[i].first] = i;
    }
    for(i = n; i >= 0; i--){
        if(f[i] == 0)
            f[i] = f[i + 1];
    }
    for(int lung = 1; lung <= n - l; lung++){
        int i = 1, j = 1 + lung;
        int cnt = 0;
        for(int t = 1; t <= l; t++){
            if(v[i] != v[j])
                cnt++;
            i++;
            j++;
        }
        update(i - l, cnt);
        update(j - l, cnt);
        int t;
        for(t = 1; t <= n && j <= n; t++){
            if(v[i - l] != v[j - l])
                cnt--;
            if(v[i] != v[j])
                cnt++;
            i++;
            j++;
            update(i - l, cnt);
            update(j - l, cnt);
        }
    }
    for(i = 1; i + l - 1 <= n; i++){
        for(int j = 1; j <= qq; j++){
            sol[j][i] += sol[j - 1][i];
        }
    }
    for(i = 1; i <= qq; i++){
        for(int j = 1; j + l - 1 <= n; j++){
            ans[q[i].second][j] = sol[i][j];
        }
    }
    for(i = 1; i <= qq; i++){
        for(int j = 1; j + l - 1 <= n; j++){
            cout << ans[i][j] << " ";
        }
        cout << "\n";
    }
    return 0;
}

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