Submission #983496

#	Time	Username	Problem	Language	Result	Execution time	Memory
983496		LOLOLO	Lottery (CEOI18_lot)	C++11	0 / 100	55 ms	65536 KiB

lot

#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 1e4 + 10;
int a[N], f[N], id[N];
vector <int> add[101];
vector <int> lst[N];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, l;
    cin >> n >> l;

    vector <int> cnt(n - l + 1, 0);

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

    for (int d = 1; d <= n; d++) {
        mem(f, 0);
        for (int i = n; i >= d + 1; i--) {
            f[i] = f[i + 1] + (a[i] != a[i - d]);
            if (i + l <= n + 1) {
                int cnt = f[i] - f[i + l];
                add[cnt].pb(i);
                add[cnt].pb(i - d);
            }
        }
    }

    vector <int> ask;

    int cc = 1;
    int q;
    cin >> q;

    for (int i = 0; i < q; i++) {
        int x;
        cin >> x;
        if (id[x] == 0) {
            id[x] = cc;
            cc++;
        }

        ask.pb(x);
    }

    for (int i = 0; i <= l; i++) {
        for (auto x : add[i]) {
            cnt[x - 1]++;
        }

        if (id[i])
            lst[id[i]] = cnt;
    }

    for (auto x : ask) {
        for (auto t : lst[id[x]])
            cout << t << " ";

        cout << '\n';
    }

    return 0;
}   

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