Submission #1188965

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188965		vito	Sličnost (COI23_slicnost)	C++20	14 / 100	3 ms	580 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define F first
#define S second
#define sz(x) int(x.size())
const int MAX=5005;
const int OFF=(1<<12);
int n, k, q;
int a[MAX], b[MAX], ib[MAX];
int d, f;
pair<int, ll> merge(pair<int, ll> &A, pair<int, ll> &B) {
	pair<int, ll> ret;
	ret.F=max(A.F, B.F);
	if(A.F<B.F) {
		ret.S=B.S;
	}
	else if(A.F>B.F) {
		ret.S=A.S;
	}
	else {
		ret.S=A.S+B.S;
	}
	return ret;
}
pair<int, ll> seg[2*OFF];
int prop[2*OFF];
void upd(int l, int r, int lo=0, int hi=OFF, int v=1) {
	seg[v].F+=prop[v];
	if(v<OFF) {
		prop[2*v]+=prop[v];
		prop[2*v+1]+=prop[v];
	}
	prop[v]=0;
	if(l>=hi || r<=lo) {
		return;
	}
	if(l<=lo && hi<=r) {
		seg[v].F+=d;
		if(v<OFF) {
			prop[2*v]+=d;
			prop[2*v+1]+=d;
		}
		return;
	}
	int m=(lo+hi)/2;
	upd(l, r, lo, m, 2*v);
	upd(l, r, m, hi, 2*v+1);
	seg[v]=merge(seg[2*v], seg[2*v+1]);
}
signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> k >> q;
	for(int i=k-1; i<n; i++) {
		seg[i+OFF]=make_pair(0, 1);
	}
	for(int i=OFF-1; i>=1; i--) {
		seg[i]=merge(seg[2*i], seg[2*i+1]);
	}
	for(int i=1; i<=n; i++) {
		cin >> a[i];
	}
	for(int i=1; i<=n; i++) {
		cin >> b[i];
		ib[b[i]]=i;
	}
	vector<ll> out(n+5);
	d=+1;
	for(int i=1; i<=k; i++) {
		int L=ib[a[i]]-1;
		int R=min(n-1, L+k-1);
		upd(max(k-1, L), R+1);
	}
	out[seg[1].F]+=seg[1].S;
	for(int i=2; i<=n-k+1; i++) {
		d=-1;
		int L=ib[a[i-1]]-1;
		int R=min(n-1, L+k-1);
		upd(max(k-1, L), R+1);
		d=+1;
		L=ib[a[i+k-1]]-1;
		R=min(n-1, L+k-1);
		upd(max(k-1, L), R+1);
		out[seg[1].F]+=seg[1].S;
	}
	for(int i=n; i>=1; i--) {
		if(out[i]>0) {
			cout << i << ' ' << out[i] << '\n';
			break;
		}
	}
	while(q--) {
		for(int i=k-1; i<n; i++) {
			seg[i+OFF]=make_pair(0, 1);
		}
		for(int i=OFF-1; i>=1; i--) {
			seg[i]=merge(seg[2*i], seg[2*i+1]);
		}
		for(int i=1; i<=n; i++) {
			out[i]=0;
		}
		for(int i=1; i<2*OFF; i++) {
			prop[i]=0;
		}
		d=+1;
		int t;
		cin >> t;
		swap(a[t], a[t+1]);
		for(int i=1; i<=k; i++) {
			int L=ib[a[i]]-1;
			int R=min(n-1, L+k-1);
			upd(max(k-1, L), R+1);
		}
		out[seg[1].F]+=seg[1].S;
		for(int i=2; i<=n-k+1; i++) {
			d=-1;
			int L=ib[a[i-1]]-1;
			int R=min(n-1, L+k-1);
			upd(max(k-1, L), R+1);
			d=+1;
			L=ib[a[i+k-1]]-1;
			R=min(n-1, L+k-1);
			upd(max(k-1, L), R+1);
			out[seg[1].F]+=seg[1].S;
		}
		for(int i=n; i>=1; i--) {
			if(out[i]>0) {
				cout << i << ' ' << out[i] << '\n';
				break;
			}
		}
	}
	return 0;
}

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