Submission #1086371

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086371		juicy	Lottery (CEOI18_lot)	C++17	100 / 100	355 ms	8500 KiB

lot

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 10005, Q = 105;

int n, l, q;
int a[N], qu[Q], b[Q], id[N], pf[N], res[N][Q];

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> l; --l;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  cin >> q;
  for (int i = 1; i <= q; ++i) {
    cin >> qu[i];
    b[i] = qu[i];
  }
  sort(b + 1, b + q + 1);
  for (int i = 1, j = 0; i <= n; ++i) {
    while (j <= q && b[j] < i) {
      ++j;
    }
    id[i] = j;
  }
  for (int d = 1; d <= n; ++d) {
    for (int i = 1; i + d <= n; ++i) {
      pf[i] = pf[i - 1] + (a[i] != a[i + d]);
    }
    for (int i = 1; i + d + l <= n; ++i) {
      int k = pf[i + l] - pf[i - 1];
      ++res[i][id[k]];
      ++res[i + d][id[k]];
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= q; ++j) {
      res[i][j] += res[i][j - 1];
    }
  }
  for (int i = 1; i <= q; ++i) {
    for (int j = 1; j + l <= n; ++j) {
      cout << res[j][id[qu[i]]] << " ";
    }
    cout << "\n";
  }
  return 0;
}

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