Submission #1114191

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114191		NotLinux	Sličnost (COI23_slicnost)	C++17	34 / 100	3054 ms	10648 KiB

Main

// Author : FatihCihan
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
void solve(){
	int n,k,query;
	cin >> n >> k >> query;
	int p[n] , q[n] , pos[n];
	for(int i = 0;i<n;i++){
		cin >> p[i];
		p[i]--;
	}
	for(int i = 0;i<n;i++){
		cin >> q[i];
		q[i]--;
		pos[q[i]] = i;
	}
	map < int , int > mpa;
	auto calc = [&](int ind , bool typ){// ans for the segment [ind , ind + k - 1]
		// cout << "calc : " << ind << " , " << typ << endl;
		vector < int > v;
		for(int i = ind;i<=ind+k-1;i++){
			v.push_back(pos[p[i]]);
		}
		sort(all(v));
		// cout << "ind : " << ind << endl;
		// cout << "v : ";for(auto itr : v)cout << itr << " ";cout << endl;
		int rp = 0;
		for(int i = 0;i<sz(v);i++){
			while(rp < sz(v) and (v[rp] - v[i]) < k)rp++;
			int lb = max(0ll , v[rp-1] - k + 1);
			int ub = min(n - k , v[i]);
			mpa[rp - i] += (typ ? 1 : -1) * (ub - lb + 1);
			// cout << rp - i << " : " << (ub - lb + 1) << " , " << typ << endl;
		}
	};
	auto answer = [&]{
		while((*(--mpa.end())).second == 0)mpa.erase(--mpa.end());
		cout << (*(--mpa.end())).first << " " << (*(--mpa.end())).second << '\n';
	};
	for(int i = 0;i<n-k+1;i++){
		calc(i , 1);
	}
	answer();
	while(query--){
		int ti;
		cin >> ti;
		ti--;
		if((ti - k + 1) >= 0)calc(ti - k + 1 , 0);
		if((ti + 1) <= (n-k))calc(ti + 1 , 0);
		swap(p[ti] , p[ti + 1]);
		if((ti - k + 1) >= 0)calc(ti - k + 1 , 1);
		if((ti + 1) <= (n-k))calc(ti + 1 , 1);
		answer();
	}
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
	cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl;
}

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