Submission #1282775

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282775		julia_08	Lottery (CEOI18_lot)	C++20	60 / 100	225 ms	4936 KiB

lot

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

const int MAXN = 1e4 + 10;
const int MAXQ = 110;

int a[MAXN];

int ans[MAXN][MAXQ];

int k[MAXN], ind[MAXQ];

int main(){
  cin.tie(0)->sync_with_stdio(0);

  int n, l; cin >> n >> l;

  for(int i=1; i<=n; i++) cin >> a[i];

  int q; cin >> q;

  vector<int> queries;

  for(int i=0; i<q; i++){
    int x; cin >> x;
    k[i] = l - x;
    queries.push_back(k[i]);
  }

  sort(queries.begin(), queries.end());
  queries.erase(unique(queries.begin(), queries.end()), queries.end());

  for(int i=0; i<q; i++){
    ind[i] = lower_bound(queries.begin(), queries.end(), k[i]) - queries.begin();
  }

  for(int d=1; d<n; d++){
    
    int p = 0;

    int sum = 0, id = -1;

    for(int i=1; i<=(n - l + 1 - d); i++){

      while(p < i + l - 1){

        p ++;

        if(p + d <= n) sum += (a[p] == a[p + d]);
        if(id + 1 < (int) queries.size()) if(sum >= queries[id + 1]) id ++;

      }

      if(id >= 0){
        ans[i][id] ++;
        ans[i + d][id] ++;
      }
  
      if(i + d <= n) sum -= (a[i] == a[i + d]); 
      if(id >= 0) if(sum < queries[id]) id --;

    }

  }

  for(int i=1; i<=n; i++){
    for(int j=((int) queries.size() - 2); j>=0; j--){
      ans[i][j] += ans[i][j + 1];
    }
  }

  for(int i=0; i<q; i++){
    for(int j=1; j<=(n - l + 1); j++) cout << ans[j][ind[i]] << " ";
    cout << "\n";
  }

  return 0;
}

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