Submission #973049

#	Time	Username	Problem	Language	Result	Execution time	Memory
973049		efedmrlr	Lottery (CEOI18_lot)	C++17	100 / 100	629 ms	8788 KiB

lot

#include <bits/stdc++.h>

#define lli long long int
#define pb push_back
#define MP make_pair
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)
#define ld long double

using namespace std;

const int N = 1e4 + 2;
const int INF = 1e9 + 500;

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

int n, l, q;
vector<int> a(N, 0);
vector<array<int, 2> > qu;
vector<int> mpp;
vector<vector<int> > prec;
void solve() {
    cin >> n >> l;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    cin >> q;
    qu.resize(q);
    REP(i, q) {
        cin >> qu[i][0];
        qu[i][1] = i;
    }
    sort(all(qu));
    mpp.assign(l + 1, 0);
    int ind = 0;
    for(int i = 0; i <= l; i++) {
        if(ind < qu.size() && qu[ind][0] < i) {
            ind++;
        }
        mpp[i] = ind;
    } ind++;
    // cerr << ind << "\n";
    prec.assign(n + 1, vector<int>(ind, 0));
    int beg = 1;
    for(int s = 2; s <= n - l + 1; s++) {
        int sum = 0;
        for(int i = 0; i < l; i++) {
            if(a[beg + i] != a[s + i]) {
                sum++;
            }
        }
        // cerr << "sum:" << sum << endl;
        prec[1][mpp[sum]]++;
        prec[s][mpp[sum]]++;
        for(int i = l; i <= n; i++) {
            if(s + i > n) break;
            if(a[beg + i] != a[s + i]) {
                sum++;
            }
            if(a[beg + i - l] != a[s + i - l]) {
                sum--;
            }
            prec[beg + i - l + 1][mpp[sum]]++;
            prec[s + i - l + 1][mpp[sum]]++;
        }
    }

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j < ind; j++) {
            prec[i][j] += prec[i][j - 1];
        }
    }
    for(int z = 0; z < q; z++) {
        swap(qu[z][0], qu[z][1]);
    }
    sort(all(qu));
    for(auto c : qu) {
        for(int i = 1; i <= n - l + 1; i++) {
            cout << prec[i][mpp[c[1]]] << " ";
        }
        cout << "\n";
    }
}

signed main() {
    fastio();
    solve();
}

Compilation message (stderr)

lot.cpp: In function 'void solve()':
lot.cpp:41:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         if(ind < qu.size() && qu[ind][0] < i) {
      |            ~~~~^~~~~~~~~~~

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