Submission #482504

#	Time	Username	Problem	Language	Result	Execution time	Memory
482504		ArianKheirandish	Lottery (CEOI18_lot)	C++14	100 / 100	1502 ms	13652 KiB

lot

// in the name of God//

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x)  x.begin(),x.end()

const int maxn = 1e4 + 20;
int n, q, l, a[maxn];
ll pr[maxn][120];
vector<int> v, qu;

void solve(int u, int v){
  int res(0);
  for(int i = 0 ; i < l ; i ++)
    if(a[u + i] ^ a[v + i])
      res = res + 1;

  //dp[u][v] = dp[v][u] = res;
}

int main(){
  ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  cin >> n >> l;
  for(int i = 0 ; i < n ; i ++)
    cin >> a[i];
  
  cin >> q;

  for(int i = 0 ; i < q ; i ++){
    int k;
    cin >> k;
    qu.push_back(k);
    v.push_back(k);
  }

  sort(all(v));
  v.resize(unique(all(v)) - v.begin());

    for(int d = 1 ; d < n ; d ++){
        vector<int> ps(n + 5);

        for(int i = 0; i + d < n; i ++)
            if(a[i] == a[i + d])
                ps[max(0, i - l + 1)] ++,
                ps[i + 1] --;

        for(int i = 0; i < n; ++i){
            if(i >= 1)
                ps[i] = ps[i] + ps[i - 1];

            if(i + 1 + d + l - 1 <= n){
                int x = lower_bound(all(v), l - ps[i]) - v.begin();
                pr[i][x] ++;
                pr[i + d][x] ++;
            }
        }

    }

    for(int i = 0 ; i < n ; i ++)
        for(int j = 1 ; j < v.size() ; j ++)
            pr[i][j] = pr[i][j] + pr[i][j - 1];

    for(int i = 0; i < q ; i ++){
        int x = lower_bound(all(v), qu[i]) - v.begin();
        for(int j = 0 ; j + l <= n ; j ++)
            cout << pr[j][x] << ' ';
        cout << '\n';
    }

  return 0;
}

/*
  Hasbi Allah  
*/

Compilation message (stderr)

lot.cpp: In function 'int main()':
lot.cpp:62:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for(int j = 1 ; j < v.size() ; j ++)
      |                         ~~^~~~~~~~~~

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