Submission #1114269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114269		epicci23	Sličnost (COI23_slicnost)	C++17	17 / 100	250 ms	199112 KiB

Main

#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int N = 5005;

void _(){
  int n,k,q;
  cin >> n >> k >> q;
  int a[n+5],b[n+5];
  for(int i=1;i<=n;i++) cin >> a[i];
  for(int i=1;i<=n;i++) cin >> b[i];
  
  bitset<N> bs[N];

  for(int i=1;i+k-1<=n;i++) for(int j=i;j<=i+k-1;j++) bs[i][a[j]]=1;
  	
  int ans[n+5][n+5],tot[n+5];
  memset(ans,-1,sizeof(ans));
  memset(tot,0,sizeof(tot));
  

  for(int i=1;i+k-1<=n;i++){
  	int res = 0,p = 0;
  	while(p<n){
  	  p++;
  	  if(bs[i][b[p]]) res++;
  	  if(p>k && bs[i][b[p-k]]) res--;
  	  if(p>=k){
  	  	ans[i][p-k+1]=res;
  	  	tot[res]++;
  	  }
  	}
  }
  
  for(int i=k;i>=0;i--){
  	if(tot[i]){
  	  cout << i << ' ' << tot[i] << '\n';
  	  break;
  	}
  }

  while(q--){
  	int ind; cin >> ind;
   
    for(int i=1;i<=n;i++) if(ans[ind+1][i]!=-1) tot[ans[ind+1][i]]--;
    if(ind>=k){
    	for(int i=1;i<=n;i++) if(ans[ind-k+1][i]!=-1) tot[ans[ind-k+1][i]]--;
    }

    bs[ind+1][a[ind+1]]=0;
    if(ind>=k) bs[ind-k+1][a[ind]]=0;
    swap(a[ind],a[ind+1]);
    bs[ind+1][a[ind+1]]=1;
    if(ind>=k) bs[ind-k+1][a[ind]]=1;
    
    int p = 0, res = 0;
    while(p<n){
  	  p++;
  	  if(bs[ind+1][b[p]]) res++;
  	  if(p>k && bs[ind+1][b[p-k]]) res--;
  	  if(p>=k){
  	  	//cout << ind+1 << ' ' << p-k+1 << ' ' << res << '\n';
  	  	ans[ind+1][p-k+1]=res;
  	  	tot[res]++;
  	  }
  	}
    
    if(ind>=k){
	    p = 0, res = 0;
	    while(p<n){
	  	  p++;
	  	  if(bs[ind-k+1][b[p]]) res++;
	  	  if(p>k && bs[ind-k+1][b[p-k]]) res--;
	  	  if(p>=k){
	  	  	//cout << ind-k+1 << ' ' << p-k+1 << ' ' << res << '\n';
	  	  	ans[ind-k+1][p-k+1]=res;
	  	  	tot[res]++;
	  	  }
	  	}
    } 

    for(int i=k;i>=0;i--){
     if(tot[i]){
  	  cout << i << ' ' << tot[i] << '\n';
  	  break;
  	 }
    }
  }
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 0 / 33
• Subtask 4: 0 / 7
• Subtask 5: 0 / 10
• Subtask 6: 0 / 33