Submission #1188744

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188744		vito	Sličnost (COI23_slicnost)	C++20	17 / 100	93 ms	4456 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=1e5+5;
const int OFF=(1<<17);
int n, k, q;
int a[MAX], b[MAX], ib[MAX];
int d, f;
// (suma podstabla, maximum za sumu - prije k i koliko ih je takvih)
pair<int, int> merge(pair<int, int> A, pair<int, int> B) {
	pair<int, int> 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, int> 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; // d je -1 ili 1
		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;
	}
	// cout << seg[1].F << ' ' << seg[1].S << '\n';
	vector<int> out(n+5);
	// d je +-1
	d=+1;
	for(int i=1; i<=k; i++) {
		int L=ib[a[i]]-1;
		int R=min(n-1, L+k-1);
		// cout << max(k-1, L) << ' ' << R << " +1\n";
		upd(max(k-1, L), R+1);
	}
	// for(int i=1; i<2*OFF; i++) {
	// 	cout << i << ": " << seg[i].F << ' ' << seg[i].S << '\n';
	// }
	// return 0;
	out[seg[1].F]+=seg[1].S;
	// cout << seg[1].F << ' ' << seg[1].S << '\n';
	// cout << '\n';
	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);
		// cout << max(L, k-1) << ' ' << R << " -1\n";
		upd(max(k-1, L), R+1);
		d=+1;
		L=ib[a[i+k-1]]-1;
		R=min(n-1, L+k-1);
		// cout << max(k-1, L) << ' ' << R << " +1\n";
		upd(max(k-1, L), R+1);
		// cout << seg[1].F << ' ' << seg[1].S << '\n';
		out[seg[1].F]+=seg[1].S;
		// return 0;
	}
	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: 10 / 10
• Subtask 3: 0 / 33
• Subtask 4: 0 / 7
• Subtask 5: 0 / 10
• Subtask 6: 0 / 33