Submission #147673

#	Time	Username	Problem	Language	Result	Execution time	Memory
147673		forestryks	Lottery (CEOI18_lot)	C++14	100 / 100	951 ms	12664 KiB

lot

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
#define rep(i, n) for (int (i) = 0; (i) < (n); ++(i))
#define all(x) (x).begin(), (x).end()
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

const int MAXN = 1e4 + 5;
const int MAXQ = 105;
int n, k, m;
int a[MAXN];
vector<int> q[MAXN];
vector<int> v;
int res[MAXN][MAXQ];
int ans[MAXQ][MAXN];

int main() {
    FAST_IO;
    cin >> n >> k;
    rep(i, n) {
        cin >> a[i];
    }
    cin >> m;
    rep(i, m) {
        int t;
        cin >> t;
        q[t].push_back(i);
    }

    rep(i, n + 1) {
        if (!q[i].empty()) {
            v.push_back(i);
        }
    }
    v.push_back(1e9);

    for (int off = 1; off + k <= n; ++off) {
        int ptr = 0;
        int c = 0;
        for (int i = 0; i < k; ++i) {
            if (a[i] != a[off + i]) {
                c++;
                while (v[ptr] < c) {
                    ptr++;
                }
            }
        }

        res[0][ptr]++;
        res[off][ptr]++;

        for (int i = 1; i + off + k <= n; ++i) {
            if (a[i - 1] != a[off + i - 1]) {
                c--;
                while (ptr > 0 && v[ptr - 1] >= c) {
                    ptr--;
                }
            }
            if (a[i + k - 1] != a[i + off + k - 1]) {
                c++;
                while (v[ptr] < c) {
                    ptr++;
                }
            }

            res[i][ptr]++;
            res[i + off][ptr]++;
        }
    }

    rep(i, n) {
        for (int j = 1; j < v.size(); ++j) {
            res[i][j] += res[i][j - 1];
        }
    }
    
    int c = 0;
    rep(i, n + 1) {
        if (q[i].empty()) continue;
        for (auto t : q[i]) {
            rep(j, n) {
                ans[t][j] = res[j][c];
            }
        }
        c++;
    }

    rep(i, m) {
        rep(j, n - k + 1) {
            cout << ans[i][j] << ' ';
        }
        cout << '\n';
    }
}

Compilation message (stderr)

lot.cpp: In function 'int main()':
lot.cpp:75:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 1; j < v.size(); ++j) {
                         ~~^~~~~~~~~~

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