oj.uz

Submission #949518

# Submission time Handle Problem Language Result Execution time Memory
949518 2024-03-19T10:12:58 Z glebustim Lottery (CEOI18_lot) C++17
35 / 100
 400 ms 1368 KB 
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(a) a.begin(), a.end()
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;
using oset = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;

int main() {
    fast;
    int n, l;
    cin >> n >> l;
    vi a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    int q;
    cin >> q;
    vector<pii> qs(q);
    for (int i = 0; i < q; ++i) {
        cin >> qs[i].first;
        qs[i].second = i;
    }
    sort(all(qs));
    vi g(n + 1);
    for (int i = 0; i <= n; ++i)
        g[i] = lower_bound(all(qs), make_pair(i, 0)) - qs.begin();
    vector<vi> d(n, vi(q, 0));
    for (int k = 1; k < n; ++k) {
        vi b(n + 1, 0);
        for (int i = 0; i + k < n; ++i) {
            int j = i + k;
            if (a[i] == a[j])
                continue;
            int lf = max(i - l + 1, 0), rg = i - max(j + l - n, 0);
            if (lf <= rg) {
                ++b[lf];
                --b[rg + 1];
            }
        }
        int x = 0;
        for (int i = 0; i + k + l <= n; ++i) {
            int j = i + k;
            x += b[i];
            ++d[i][g[x]];
            ++d[j][g[x]];
        }
    }
    vector<vi> ans(q, vi(n - l + 1, 0));
    for (int i = 0; i <= n - l; ++i) {
        int x = 0;
        for (int j = 0; j < q; ++j) {
            x += d[i][j];
            ans[qs[j].second][i] = x;
        }
    }
    for (int i = 0; i < q; ++i) {
        for (int j = 0; j <= n - l; ++j)
            cout << ans[i][j] << ' ';
        cout << '\n';
    }
}

Subtask #1
0 / 25.0

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

Subtask #2
0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 1112 KB Output is correct
2 Correct 400 ms 1116 KB Output is correct
3 Correct 261 ms 1132 KB Output is correct
4 Correct 223 ms 1364 KB Output is correct
5 Correct 109 ms 1204 KB Output is correct
6 Correct 215 ms 1208 KB Output is correct
7 Correct 75 ms 1112 KB Output is correct
8 Correct 123 ms 1368 KB Output is correct
9 Correct 220 ms 1116 KB Output is correct
10 Correct 224 ms 1200 KB Output is correct
11 Correct 14 ms 664 KB Output is correct
12 Correct 153 ms 1148 KB Output is correct
13 Correct 151 ms 1212 KB Output is correct
14 Correct 139 ms 1232 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 1112 KB Output is correct
2 Correct 400 ms 1116 KB Output is correct
3 Correct 261 ms 1132 KB Output is correct
4 Correct 223 ms 1364 KB Output is correct
5 Correct 109 ms 1204 KB Output is correct
6 Correct 215 ms 1208 KB Output is correct
7 Correct 75 ms 1112 KB Output is correct
8 Correct 123 ms 1368 KB Output is correct
9 Correct 220 ms 1116 KB Output is correct
10 Correct 224 ms 1200 KB Output is correct
11 Correct 14 ms 664 KB Output is correct
12 Correct 153 ms 1148 KB Output is correct
13 Correct 151 ms 1212 KB Output is correct
14 Correct 139 ms 1232 KB Output is correct
15 Correct 256 ms 1132 KB Output is correct
16 Correct 212 ms 1208 KB Output is correct
17 Correct 232 ms 1112 KB Output is correct
18 Correct 241 ms 1360 KB Output is correct
19 Correct 255 ms 1212 KB Output is correct
20 Correct 238 ms 1208 KB Output is correct
21 Correct 224 ms 1216 KB Output is correct

Subtask #5
0 / 20.0

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