Submission #698982

#	Time	Username	Problem	Language	Result	Execution time	Memory
698982		dattranxxx	Lottery (CEOI18_lot)	C++11	35 / 100	335 ms	596 KiB

lot

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

const int N = 1e4 + 5;
int a[N];
int n, l, q;

int ans[105][N];
pair<int, int> kq[105];

#define fi first
#define se second

int main() {
  cin.tie(0)->sync_with_stdio(0); cout.tie(0);
  cin >> n >> l;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  
  cin >> q;
  for (int i = 1; i <= q; ++i) {
    cin >> kq[i].fi;
    kq[i].se = i;
  }
  kq[q + 1] = make_pair(n + 1, q + 1);
  
  sort(kq + 1, kq + q + 1);
  
  for (int k = 1; l + k <= n; ++k) {
    
    int dif = 0;
    for (int i = 1; i <= l; ++i) {
      dif += a[i] != a[i + k];
    }
    
    int j = 1;
    while (kq[j].fi < dif) j++;
    
    ans[kq[j].se][1]++;
    ans[kq[j].se][1 + k]++;
    
    
    for (int i = 2; i + k + l - 1 <= n; ++i) {
      dif -= a[i - 1] != a[i + k - 1];
      dif += a[i + l - 1] != a[i + k + l - 1];
      while (kq[j].fi < dif) j++;
      while (j - 1 >= 1 && kq[j - 1].fi >= dif) j--;
      ans[kq[j].se][i]++;
      ans[kq[j].se][i + k]++;
    }
  }
  
  for (int i = 1; i <= q; ++i) {
    for (int j = 1; j <= n - l + 1; ++j) {
      ans[i][j] += ans[i - 1][j];
      cout << ans[i][j] << ' ';
    }
    cout << '\n';
  }
  
	return 0;
}

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