oj.uz

Submission #482504

# Submission time Handle Problem Language Result Execution time Memory
482504 2021-10-25T05:31:47 Z ArianKheirandish Lottery (CEOI18_lot) C++14
100 / 100
 1502 ms 13652 KB 
// 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

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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 408 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 1 ms 588 KB Output is correct
12 Correct 2 ms 588 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 408 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 1 ms 588 KB Output is correct
12 Correct 2 ms 588 KB Output is correct
13 Correct 30 ms 2196 KB Output is correct
14 Correct 20 ms 2236 KB Output is correct
15 Correct 20 ms 2240 KB Output is correct
16 Correct 28 ms 2256 KB Output is correct
17 Correct 26 ms 2216 KB Output is correct
18 Correct 26 ms 2160 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 866 ms 9764 KB Output is correct
2 Correct 795 ms 9784 KB Output is correct
3 Correct 619 ms 9804 KB Output is correct
4 Correct 543 ms 9696 KB Output is correct
5 Correct 377 ms 5196 KB Output is correct
6 Correct 514 ms 9220 KB Output is correct
7 Correct 408 ms 5200 KB Output is correct
8 Correct 424 ms 7072 KB Output is correct
9 Correct 577 ms 9548 KB Output is correct
10 Correct 557 ms 9680 KB Output is correct
11 Correct 40 ms 2124 KB Output is correct
12 Correct 366 ms 7012 KB Output is correct
13 Correct 381 ms 6036 KB Output is correct
14 Correct 400 ms 5964 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 866 ms 9764 KB Output is correct
2 Correct 795 ms 9784 KB Output is correct
3 Correct 619 ms 9804 KB Output is correct
4 Correct 543 ms 9696 KB Output is correct
5 Correct 377 ms 5196 KB Output is correct
6 Correct 514 ms 9220 KB Output is correct
7 Correct 408 ms 5200 KB Output is correct
8 Correct 424 ms 7072 KB Output is correct
9 Correct 577 ms 9548 KB Output is correct
10 Correct 557 ms 9680 KB Output is correct
11 Correct 40 ms 2124 KB Output is correct
12 Correct 366 ms 7012 KB Output is correct
13 Correct 381 ms 6036 KB Output is correct
14 Correct 400 ms 5964 KB Output is correct
15 Correct 528 ms 9484 KB Output is correct
16 Correct 500 ms 8940 KB Output is correct
17 Correct 566 ms 9856 KB Output is correct
18 Correct 536 ms 9764 KB Output is correct
19 Correct 570 ms 9772 KB Output is correct
20 Correct 572 ms 9776 KB Output is correct
21 Correct 547 ms 9784 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 408 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 1 ms 588 KB Output is correct
12 Correct 2 ms 588 KB Output is correct
13 Correct 30 ms 2196 KB Output is correct
14 Correct 20 ms 2236 KB Output is correct
15 Correct 20 ms 2240 KB Output is correct
16 Correct 28 ms 2256 KB Output is correct
17 Correct 26 ms 2216 KB Output is correct
18 Correct 26 ms 2160 KB Output is correct
19 Correct 866 ms 9764 KB Output is correct
20 Correct 795 ms 9784 KB Output is correct
21 Correct 619 ms 9804 KB Output is correct
22 Correct 543 ms 9696 KB Output is correct
23 Correct 377 ms 5196 KB Output is correct
24 Correct 514 ms 9220 KB Output is correct
25 Correct 408 ms 5200 KB Output is correct
26 Correct 424 ms 7072 KB Output is correct
27 Correct 577 ms 9548 KB Output is correct
28 Correct 557 ms 9680 KB Output is correct
29 Correct 40 ms 2124 KB Output is correct
30 Correct 366 ms 7012 KB Output is correct
31 Correct 381 ms 6036 KB Output is correct
32 Correct 400 ms 5964 KB Output is correct
33 Correct 528 ms 9484 KB Output is correct
34 Correct 500 ms 8940 KB Output is correct
35 Correct 566 ms 9856 KB Output is correct
36 Correct 536 ms 9764 KB Output is correct
37 Correct 570 ms 9772 KB Output is correct
38 Correct 572 ms 9776 KB Output is correct
39 Correct 547 ms 9784 KB Output is correct
40 Correct 994 ms 10588 KB Output is correct
41 Correct 299 ms 9872 KB Output is correct
42 Correct 694 ms 10584 KB Output is correct
43 Correct 651 ms 10308 KB Output is correct
44 Correct 691 ms 10308 KB Output is correct
45 Correct 1502 ms 13516 KB Output is correct
46 Correct 299 ms 10120 KB Output is correct
47 Correct 873 ms 13652 KB Output is correct
48 Correct 804 ms 11892 KB Output is correct
49 Correct 823 ms 12528 KB Output is correct