Submission #983525

#	Time	Username	Problem	Language	Result	Execution time	Memory
983525		LOLOLO	Lottery (CEOI18_lot)	C++11	100 / 100	238 ms	12628 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], nxt[N];
int add[110][N];
vector <int> lst[110];

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

    mem(nxt, 0x3f);
    int n, l;
    cin >> n >> l;

    nxt[l + 1] = l + 1;
    vector <int> cnt(n - l + 1, 0);

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

    vector <int> ask;

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

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

        ask.pb(x);
    }

    for (int i = l; i >= 0; i--)
        nxt[i] = min(nxt[i + 1], nxt[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 = id[nxt[f[i] - f[i + l]]];
                add[cnt][i - 1]++;
                add[cnt][i - d - 1]++;
            }
        }
    }

    for (int i = 0; i <= l; i++) {
        if (id[i]) {
            for (int j = 0; j < n - l + 1; j++) {
                cnt[j] += add[id[i]][j];
            }

            lst[id[i]] = cnt;  
        }
    }

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

        cout << '\n';
    }

    return 0;
}   

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