Submission #430487

#	Time	Username	Problem	Language	Result	Execution time	Memory
430487		Pety	Lottery (CEOI18_lot)	C++14	100 / 100	876 ms	8260 KiB

lot

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


int n, l, a[100002], poz[100002], q[102], ans[102], cnt[10002][102], q2[102];
int ask (int x, int y) {
  int ans = 0;
  for (int i = 1; i <= l; i++)
    if (a[x + i - 1] != a[y + i - 1])
      ans++;
  return ans;
}

int main()
{
  cin >> n >> l;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  int Q;
  cin >> Q;
  for (int i = 1; i <= Q; i++) {
    cin >> q[i];
    q2[i] = q[i];
  }
  sort(q + 1, q + Q + 1);
  int nr = 0;
  for (int i = 1; i <= Q; i++)
    if (i == 1 || q[i] != q[i - 1])
      q[++nr] = q[i];
  for (int i = 1; i <= n; i++)
    poz[i] = lower_bound(q + 1, q + nr + 1, i) - q;
  for (int i = 2; i <= n - l + 1; i++) {
    int val = ask(1, i);
    cnt[1][poz[val]]++;
    cnt[i][poz[val]]++;
    for (int j = l + 1; j + i - 1 <= n; j++) {
      if (a[j - l] != a[i + j - l - 1])
        val--;
      if (a[j] != a[j + i - 1])
        val++;
      cnt[j - l + 1][poz[val]]++;
      cnt[j - l + i][poz[val]]++;
    }
  }
  for (int i = 1; i <= n - l + 1; i++)
    for (int j = 1; j <= Q; j++)
      cnt[i][j] += cnt[i][j - 1];
  for (int i = 1; i <= Q; i++) {
    int x = lower_bound(q + 1, q + nr + 1, q2[i]) - q;
    for (int j = 1; j <= n - l + 1; j++)
      cout << cnt[j][x] << " ";
    cout << "\n";
  }
  return 0;
}

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