Submission #1190935

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190935		kerem	Sličnost (COI23_slicnost)	C++20	17 / 100	1086 ms	189624 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define fr first
#define sc second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define inf 1e15
#define N 5000
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef tuple<int,int,int> tiii;
typedef pair<int,int> pii;

int d[N+5][N+5],mx[N+5],mp[N+5];
multiset<int> ms;
int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	
	int n,k,q;
	cin >> n >> k >> q;
	int a[n+1],b[n+1];
	for(int i=1;i<=n;i++)
		cin >> a[i];
	for(int i=1;i<=n;i++)
		cin >> b[i];
	for(int i=1;i<=n-k+1;i++){
		if(i==1){
			for(int it=1;it<=k;it++)
				mp[a[it]]++;
		}
		else mp[a[i-1]]--,mp[a[i+k-1]]++;
		int t=0;
		for(int j=1;j<=n-k+1;j++){
			if(j==1){
				for(int it=1;it<=k;it++)
					t+=mp[b[it]];
			}
			else t+=mp[b[j+k-1]]-mp[b[j-1]];
			d[i][t]++;
			mx[i]=max(mx[i],t);
		}
		ms.insert(mx[i]);
	}
	int ans=0,Max=*(--ms.end());
	for(int i=1;i<=n-k+1;i++)
		ans+=d[i][Max];
	cout << Max sp ans << endl;
	while(q--){
		int x;
		cin >> x;
		swap(a[x],a[x+1]);
		if(x>=k){
			int i=x-k+1;
			for(int it=1;it<=n;it++)
				mp[it]--;
			ms.erase(ms.find(mx[i]));
			mx[i]=0;
			for(int it=1;it<=k;it++)
				d[i][it]=0;
			
			for(int it=i;it<=i+k-1;it++)
				mp[a[it]]++;
			int t=0;
			for(int j=1;j<=n-k+1;j++){
				if(j==1){
					for(int it=1;it<=k;it++)
						t+=mp[b[it]];
				}
				else t+=mp[b[j+k-1]]-mp[b[j-1]];
				d[i][t]++;
				mx[i]=max(mx[i],t);
			}
			ms.insert(mx[i]);
		}
		if(x+1<=n-k+1){
			int i=x+1;
			for(int it=1;it<=n;it++)
				mp[it]--;
			ms.erase(ms.find(mx[i]));
			mx[i]=0;
			for(int it=1;it<=k;it++)
				d[i][it]=0;
			
			for(int it=i;it<=i+k-1;it++)
				mp[a[it]]++;
			int t=0;
			for(int j=1;j<=n-k+1;j++){
				if(j==1){
					for(int it=1;it<=k;it++)
						t+=mp[b[it]];
				}
				else t+=mp[b[j+k-1]]-mp[b[j-1]];
				d[i][t]++;
				mx[i]=max(mx[i],t);
			}
			ms.insert(mx[i]);
		}
		//~ for(int i=1;i<=n-k+1;i++){
			//~ for(int j=1;j<=k;j++)
				//~ cout << d[i][j] << " ";
			//~ cout << endl;
		//~ }
		ans=0;Max=*(--ms.end());
		for(int i=1;i<=n-k+1;i++)
			ans+=d[i][Max];
		cout << Max sp ans << endl;
	}
}

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