Submission #1214267

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214267		lopkus	Lottery (CEOI18_lot)	C++20	25 / 100	88 ms	131072 KiB

lot

#include <bits/stdc++.h>

#define int int64_t

signed main() {
  int n, l;
  std::cin >> n >> l;
  std::vector<int> a(n + 1);
  for(int i = 1; i <= n; i++) {
    std::cin >> a[i];
  }
  std::vector<std::vector<int>> pref(n + 2, std::vector<int>(n + 1));
  for(int j = 1; j <= n; j++) {
    for(int i = n; i >= 1; i--) {
      pref[i][j] = pref[i + 1][j];
      if(i + j <= n) {
        pref[i][j] += (a[i] != a[i + j]);
      }
    }
  }
  int q;
  std::cin >> q;
  std::vector<int> k(q + 1);
  for(int i = 1; i <= q; i++) {
    std::cin >> k[i];
  }
  std::vector<int> now(n + 1);
  for(int i = 1; i + l - 1 <= n; i++) {
    now[i] = 0;
  }
  int N = n * n;
  std::vector<std::vector<int>> ans(q + 1);
  std::vector<int> query[N + 1];
  for(int i = 1; i <= q; i++) {
    query[k[i]].push_back(i);
  }
  std::vector<std::vector<std::pair<int, int>>> del(N + 1);
  for(int i = 1; i + l - 1 <= n; i++) {
    for(int j = i + 1; j + l - 1 <= n; j++) {
      int s = j - i;
      del[pref[i][s] - pref[i + l][s]].push_back({i, j});
    }
  }
  for(int i = 0; i <= N; i++) {
    for(auto [u, v] : del[i]) {
      now[u]++;
      now[v]++;
    }
    for(auto u : query[i]) {
      for(int j = 1; j + l - 1 <= n; j++) {
        ans[u].push_back(now[j]);
      }
    }
  }
  for(int i = 1; i <= q; i++) {
    for(auto u : ans[i]) {
      std::cout << u << " ";
    }
    std::cout << "\n";
  }
}

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