Submission #526846

#	Time	Username	Problem	Language	Result	Execution time	Memory
526846		hoanghq2004	Lottery (CEOI18_lot)	C++14	100 / 100	1319 ms	8728 KiB

lot

#include <bits/stdc++.h>
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 1e4 + 10;

int n, l, q, a[N];
int k[N], id[N];
int dist[N * 2];
int ans[N][110];

void add(int x) {
    for (int i = 0; i < n; ++i)
        if (a[i] != a[x]) ++dist[i - x + N];
}

void rev(int x) {
    for (int i = 0; i < n; ++i)
        if (a[i] != a[x]) --dist[i - x + N];
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> l;
    for (int i = 0; i < n; ++i) cin >> a[i];
    cin >> q;
    vector <int> dta;
    for (int i = 0; i < q; ++i) {
        cin >> k[i];
        dta.push_back(k[i]);
    }
    sort(dta.begin(), dta.end());
    for (int i = 0; i <= l; ++i) id[i] = lower_bound(dta.begin(), dta.end(), i) - dta.begin();
    for (int i = 0; i < l; ++i) add(i);
    for (int i = 0; i < n - l + 1; ++i) {
        for (int j = N - i; j < N + n - l + 1 - i; ++j) ++ans[i][id[dist[j]]];
        for (int j = 1; j < q; ++j) ans[i][j] += ans[i][j - 1];
        rev(i), add(i + l);
    }
    for (int i = 0; i < q; ++i) {
        for (int j = 0; j < n - l + 1; ++j) cout << ans[j][id[k[i]]] - 1 << ' ';
        cout << '\n';
    }
}

Compilation message (stderr)

lot.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
lot.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |

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