oj.uz

Submission #983490

# Submission time Handle Problem Language Result Execution time Memory
983490 2024-05-15T15:02:12 Z LOLOLO Lottery (CEOI18_lot) C++17
25 / 100
 29 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][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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 2 ms 4700 KB Output is correct
8 Correct 2 ms 11096 KB Output is correct
9 Correct 2 ms 11100 KB Output is correct
10 Correct 3 ms 11764 KB Output is correct
11 Correct 3 ms 11752 KB Output is correct
12 Correct 3 ms 11752 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 2 ms 4700 KB Output is correct
8 Correct 2 ms 11096 KB Output is correct
9 Correct 2 ms 11100 KB Output is correct
10 Correct 3 ms 11764 KB Output is correct
11 Correct 3 ms 11752 KB Output is correct
12 Correct 3 ms 11752 KB Output is correct
13 Runtime error 29 ms 65536 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 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 25 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 2 ms 2652 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 2 ms 4700 KB Output is correct
8 Correct 2 ms 11096 KB Output is correct
9 Correct 2 ms 11100 KB Output is correct
10 Correct 3 ms 11764 KB Output is correct
11 Correct 3 ms 11752 KB Output is correct
12 Correct 3 ms 11752 KB Output is correct
13 Runtime error 29 ms 65536 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -