Submission #841822

#	Time	Username	Problem	Language	Result	Execution time	Memory
841822		WLZ	Lottery (CEOI18_lot)	C++17	100 / 100	397 ms	12544 KiB

lot

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, l; cin >> n >> l;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  int q; cin >> q;
  vector< pair<int, int> > queries;
  for (int i = 0; i < q; i++) {
    int k; cin >> k;
    queries.emplace_back(k, i);
  }
  sort(queries.begin(), queries.end());
  vector< vector<int> > ans(n, vector<int>(q, 0));
  vector<int> add_to(n, -1);
  for (int i = 0; i <= l; i++) {
    auto it = lower_bound(queries.begin(), queries.end(), make_pair(i, -1));
    if (it != queries.end()) add_to[i] = it - queries.begin();
  }
  for (int k = 1; k <= n - l; k++) {
    int cnt = 0;
    for (int i = 0; i < l; i++) if (a[i] == a[i + k]) cnt++;
    for (int i = 0, j = k; j <= n - l; i++, j++) {
      if (add_to[l - cnt] != -1) ans[i][add_to[l - cnt]]++, ans[j][add_to[l - cnt]]++;
      cnt -= (a[i] == a[j]);
      if (j + l < n) cnt += (a[i + l] == a[j + l]);
    }
  }
  #ifdef DEBUG
  //for (auto &[k, i, j] : v) cerr << k << ": " << i << ' ' << j << endl;
  #endif
  for (int i = 0; i < n; i++) {
    for (int j = 1; j < q; j++) ans[i][j] += ans[i][j - 1];
  }
  vector< vector<int> > ans2(q);
  for (int i = 0; i < q; i++) {
    vector<int> tmp;
    for (int j = 0; j <= n - l; j++) tmp.push_back(ans[j][i]);
    ans2[queries[i].second] = tmp;
  }
  swap(ans, ans2);
  for (int i = 0; i < q; i++) {
    for (int j = 0; j <= n - l; j++) cout << ans[i][j] << ' ';
    cout << '\n';
  }
  return 0;
}

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