Submission #983490

#	Time	Username	Problem	Language	Result	Execution time	Memory
983490		LOLOLO	Lottery (CEOI18_lot)	C++17	25 / 100	29 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][N];
vector < pair <int, int>> add[N];
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 i = n; i >= 1; i--) {
        for (int j = n; j > i; j--) {
            f[i][j] = f[i + 1][j + 1] + (a[i] != a[j]);
            if (j + l <= n + 1) {
                int cnt = f[i][j] - f[i + l][j + l];
                add[cnt].pb({i, j});
            }
        }
    }

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

        lst[i] = cnt;
    }

    int q;
    cin >> q;

    for (int i = 0; i < q; i++) {
        int x;
        cin >> x;

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

        cout << '\n';
    }

    return 0;
}   

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