oj.uz

Submission #885419

# Submission time Handle Problem Language Result Execution time Memory
885419 2023-12-09T16:03:31 Z shenfe1 Lottery (CEOI18_lot) C++17
35 / 100
 490 ms 11096 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ld long double
#define pb push_back
#define pf push_front
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define mem(a,i) memset(a,i,sizeof(a))
#define sz(s) (int)s.size()
#define int ll
// #define int short int
#define y1 yy
#define ppb pop_back
#define lb lower_bound
#define ub upper_bound
#define gcd(a,b) __gcd(a,b)
#define in insert
#define pdd pair<ld,ld>

const int MAX=1e4+10;

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

mt19937 rng;

int n,l,q;
int a[MAX];
int c[MAX][105];
int ans[MAX][105];
pii k[MAX];
int r[MAX];

void solve(){
  cin>>n>>l;
  for(int i=1;i<=n;i++){
    cin>>a[i];
  }
  cin>>q;
  for(int i=1;i<=q;i++){
    cin>>k[i].F;
    k[i].S=i;
  }
  sort(k+1,k+q+1);
  int pos=1;
  for(int i=1;i<=l;i++){
    while(pos+1<=q&&i>k[pos].F){
      pos++;
    }
    if(pos==q&&i>k[pos].F)r[i]=q+1;
    else r[i]=pos;
  }
  for(int dif=1;dif+l<=n;dif++){
    int i=1,j=dif+1;
    int cnt=0;
    for(int k=0;k<l;k++){
      if(a[i+k]!=a[j+k]){
        cnt++;
      }
    }
    c[i][r[cnt]]++;c[j][r[cnt]]++;
    i+=l;j+=l;
    while(j<=n){
      if(a[i]!=a[j])cnt++;
      if(a[i-l]!=a[j-l])cnt--;
      c[i-l+1][r[cnt]]++;c[j-l+1][r[cnt]]++;
      i++,j++;
    }
  }
  for(int i=1;i<=q;i++){
    for(int j=1;j<=n-l+1;j++){
      c[j][i]+=c[j][i-1];
      ans[k[i].S][j]=c[j][i];
    }
  }
  for(int i=1;i<=q;i++){
    for(int j=1;j<=n-l+1;j++){
      cout<<ans[i][j]<<" ";
    }
    cout<<"\n";
  }
} 


main(){
  // freopen("color.in", "r", stdin);
  // freopen("color.out", "w", stdout);
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t=1;
  // cin>>t;
  while(t--){
    solve();
  }
}

Compilation message

lot.cpp:90:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   90 | main(){
      | ^~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Incorrect 1 ms 4440 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Incorrect 1 ms 4440 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 10836 KB Output is correct
2 Correct 490 ms 10836 KB Output is correct
3 Correct 183 ms 10864 KB Output is correct
4 Correct 144 ms 10868 KB Output is correct
5 Correct 60 ms 8892 KB Output is correct
6 Correct 141 ms 10884 KB Output is correct
7 Correct 49 ms 8988 KB Output is correct
8 Correct 81 ms 8864 KB Output is correct
9 Correct 165 ms 10884 KB Output is correct
10 Correct 154 ms 11096 KB Output is correct
11 Correct 10 ms 4444 KB Output is correct
12 Correct 80 ms 8832 KB Output is correct
13 Correct 72 ms 8884 KB Output is correct
14 Correct 82 ms 8864 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 10836 KB Output is correct
2 Correct 490 ms 10836 KB Output is correct
3 Correct 183 ms 10864 KB Output is correct
4 Correct 144 ms 10868 KB Output is correct
5 Correct 60 ms 8892 KB Output is correct
6 Correct 141 ms 10884 KB Output is correct
7 Correct 49 ms 8988 KB Output is correct
8 Correct 81 ms 8864 KB Output is correct
9 Correct 165 ms 10884 KB Output is correct
10 Correct 154 ms 11096 KB Output is correct
11 Correct 10 ms 4444 KB Output is correct
12 Correct 80 ms 8832 KB Output is correct
13 Correct 72 ms 8884 KB Output is correct
14 Correct 82 ms 8864 KB Output is correct
15 Correct 195 ms 10832 KB Output is correct
16 Correct 136 ms 10836 KB Output is correct
17 Correct 164 ms 10832 KB Output is correct
18 Correct 164 ms 10884 KB Output is correct
19 Correct 161 ms 10888 KB Output is correct
20 Correct 147 ms 10892 KB Output is correct
21 Correct 153 ms 10888 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Incorrect 1 ms 4440 KB Output isn't correct
9 Halted 0 ms 0 KB -