Submission #961968

#	Time	Username	Problem	Language	Result	Execution time	Memory
961968		TAhmed33	Sličnost (COI23_slicnost)	C++98	57 / 100	3012 ms	7948 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mid ((l + r) >> 1)
#define tl (node + 1)
#define tr (node + 2 * (mid - l + 1))
const int MAXN = 1e5 + 25;
struct SegmentTree {
	pair <int, int> tree[MAXN << 1];
	int lazy[MAXN << 1];
	pair <int, int> comb (pair <int, int> a, pair <int, int> b) {
		if (a.first > b.first) return a;
		if (a.first < b.first) return b;
		return {a.first, a.second + b.second};
	}
	void init (int l, int r, int node) {
		lazy[node] = 0;
		tree[node] = {0, r - l + 1};
		if (l == r) return;
		init(l, mid, tl); init(mid + 1, r, tr);
	}
	void prop (int l, int r, int node) {
		if (lazy[node] == 0) return;
		if (l != r) {
			lazy[tl] += lazy[node];
			lazy[tr] += lazy[node];
		}
		tree[node].first += lazy[node];
		lazy[node] = 0;
	}
	void update (int l, int r, int a, int b, int c, int node) {
		prop(l, r, node);
		if (l > b || r < a) return;
		if (l >= a && r <= b) {
			lazy[node] += c;
			prop(l, r, node);
			return;
		}
		update(l, mid, a, b, c, tl); update(mid + 1, r, a, b, c, tr);
		tree[node] = comb(tree[tl], tree[tr]);
	}
	pair <int, int> get (int l, int r, int a, int b, int node) {
		prop(l, r, node);
		if (l > b || r < a) return {-1, 0};
		if (l >= a && r <= b) return tree[node];
		return comb(get(l, mid, a, b, tl), get(mid + 1, r, a, b, tr));
	}
} cur;
long long n, k, q, a[MAXN], p[MAXN];
void solve () {
	cur.init(1, n, 1);
	pair <int, int> u = {0, 0};
	for (int i = 1; i <= k; i++) {
		cur.update(1, n, max(1ll, a[i] - k + 1), min(a[i], n - k + 1), 1, 1);
	}
	auto z = cur.get(1, n, 1, n, 1);
	u = z;
	for (int i = k + 1; i <= n; i++) {
		cur.update(1, n, max(1ll, a[i - k] - k + 1), min(a[i - k], n - k + 1), -1, 1);
		cur.update(1, n, max(1ll, a[i] - k + 1), min(a[i], n - k + 1), 1, 1);
		auto z = cur.get(1, n, 1, n, 1);
		u = cur.comb(u, z);
	}
	cout << u.first << " " << u.second << '\n';
}
signed main () {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> k >> q;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) {
		int x; cin >> x;
		p[x] = i;
	}
	for (int i = 1; i <= n; i++) a[i] = p[a[i]];
	solve();
	while (q--) {
		int x; cin >> x;
		swap(a[x], a[x + 1]);
		solve();
	}
}

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