oj.uz

Submission #983496

# Submission time Handle Problem Language Result Execution time Memory
983496 2024-05-15T15:13:21 Z LOLOLO Lottery (CEOI18_lot) C++11
0 / 100
 55 ms 65536 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Runtime error 1 ms 1368 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Runtime error 1 ms 1368 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 55 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 55 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Runtime error 1 ms 1368 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -