oj.uz

Submission #70886

# Submission time Handle Problem Language Result Execution time Memory
70886 2018-08-23T15:35:13 Z georgerapeanu Global Warming (CEOI18_glo) C++11
0 / 100
 9 ms 824 KB 
#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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 488 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 684 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 380 KB Output isn't correct
2 Halted 0 ms 0 KB -