Submission #70888

#	Time	Username	Problem	Language	Result	Execution time	Memory
70888		georgerapeanu	Lottery (CEOI18_lot)	C++11	100 / 100	2199 ms	8748 KiB

lot

#include <iostream>
#include <algorithm>

using namespace std;

int n,l,q;
int v[10005];
pair<int,int> queries[105];
int dp[2][10005];
int inverseeeee[105];
int ans[105][10005];

int brut(int i,int j){
    int ans = 0;
    for(int k = 0;k < l;k++){
        ans += (v[i + k] != v[j + k]);
    }
    return ans;
}


int main() {
   cin >> n >> l;
   for(int i = 1;i <= n;i++){
      cin >> v[i];
   }

   cin >> q;

   for(int i = 1;i <= q;i++){
      cin >> queries[i].first;
      queries[i].second = i;
   }

   sort(queries + 1,queries + 1 + q);

   for(int i = 1;i <= q;i++){
      inverseeeee[queries[i].second] = i;
   }

   for(int j = 2;j <= n - l + 1;j++){
      dp[1][j] = brut(1,j);
      int st = 0,dr = q + 1;
      while(dr - st > 1){
         int mid = (st + dr) / 2;
         if(queries[mid].first < dp[1][j]){
            st = mid;
         }
         else{
            dr = mid;
         }
      }
      if(dr == q + 1){
         continue;
      }
      ans[dr][1]++;
      ans[dr][j]++;
   }

   for(int i = 2,c = 0;i <= n - l + 1;i++,c ^= 1){
      for(int j = i + 1;j <= n - l + 1;j++){
         dp[c][j] = dp[c ^ 1][j - 1] - (v[i - 1] != v[j - 1]) + (v[i + l - 1] != v[j + l - 1]);
         int st = 0,dr = q + 1;
         while(dr - st > 1){
            int mid = (st + dr) / 2;
            if(queries[mid].first < dp[c][j]){
               st = mid;
            }
            else{
               dr = mid;
            }
         }
         if(dr == q + 1){
            continue;
         }
         ans[dr][i]++;
         ans[dr][j]++;
      }
   }

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

   for(int i = 1;i <= q;i++){
      for(int j = 1;j <= n - l + 1;j++){
         cout << ans[inverseeeee[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