Submission #810638

#	Time	Username	Problem	Language	Result	Execution time	Memory
810638		rainboy	Sličnost (COI23_slicnost)	C11	100 / 100	1597 ms	422484 KiB

Main

#include <stdio.h>

#define N	100000
#define LN	17	/* LN = ceil(log2(N)) */
#define N_	(1 << LN)
#define N1	(N * 2 + (N * 4 + Q * 8) * (LN + 1) + 1)
#define Q	100000

int max(int a, int b) { return a > b ? a : b; }

int ll[N1], rr[N1], ss[N1], pr[N1], kk[N1], _ = 1;

int build(int l, int r) {
	int t_ = _++;

	ss[t_] = 0, pr[t_] = 0, kk[t_] = r - l;
	if (r - l > 1) {
		int m = (l + r) / 2;

		ll[t_] = build(l, m), rr[t_] = build(m, r);
	}
	return t_;
}

void pul(int t) {
	int l = ll[t], r = rr[t];

	ss[t] = ss[l] + ss[r];
	if (pr[l] > ss[l] + pr[r])
		pr[t] = pr[l], kk[t] = kk[l];
	else if (pr[l] < ss[l] + pr[r])
		pr[t] = ss[l] + pr[r], kk[t] = kk[r];
	else
		pr[t] = pr[l], kk[t] = kk[l] + kk[r];
}

int update(int t, int l, int r, int i, int x) {
	int t_ = _++;

	if (r - l > 1) {
		int m = (l + r) / 2;

		if (i < m)
			ll[t_] = update(ll[t], l, m, i, x), rr[t_] = rr[t];
		else
			ll[t_] = ll[t], rr[t_] = update(rr[t], m, r, i, x);
		pul(t_);
	} else
		ll[t_] = ll[t], rr[t_] = rr[t], pr[t_] = ss[t_] = ss[t] + x, kk[t_] = 1;
	return t_;
}

int tt[N], n, k;

int mx[N_ * 2], n_; long long kk_[N_ * 2];

void pul_(int i) {
	int l = i << 1, r = l | 1;

	if (mx[l] > mx[r])
		mx[i] = mx[l], kk_[i] = kk_[l];
	else if (mx[l] < mx[r])
		mx[i] = mx[r], kk_[i] = kk_[r];
	else
		mx[i] = mx[l], kk_[i] = kk_[l] + kk_[r];
}

void build_() {
	int i;

	n_ = 1;
	while (n_ < n - k + 1)
		n_ <<= 1;
	for (i = 0; i < n_; i++)
		if (i < n - k + 1)
			mx[n_ + i] = pr[tt[i]], kk_[n_ + i] = kk[tt[i]];
		else
			mx[n_ + i] = 0, kk_[n_ + i] = 0;
	for (i = n_ - 1; i > 0; i--)
		pul_(i);
}

void update_(int i, int j, int x) {
	tt[i] = update(tt[i], 0, n - k + 1, j, x);
	mx[n_ + i] = pr[tt[i]], kk_[n_ + i] = kk[tt[i]];
	i += n_;
	while (i > 1)
		pul_(i >>= 1);
}

int main() {
	static int aa[N], jj[N];
	int q, i, j, a, b, t;

	scanf("%d%d%d", &n, &k, &q);
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]), aa[i]--;
	for (j = 0; j < n; j++) {
		scanf("%d", &a), a--;
		jj[a] = j;
	}
	t = build(0, n - k + 1);
	for (i = 0; i < n; i++) {
		a = aa[i], j = jj[a];
		t = update(t, 0, n - k + 1, max(j - k + 1, 0), 1);
		if (j + k < n)
			t = update(t, 0, n - k + 1, j + 1, -1);
		if (i >= k - 1) {
			tt[i - k + 1] = t;
			a = aa[i - k + 1], j = jj[a];
			t = update(t, 0, n - k + 1, max(j - k + 1, 0), -1);
			if (j + k < n)
				t = update(t, 0, n - k + 1, j + 1, 1);
		}
	}
	build_();
	printf("%d %lld\n", mx[1], kk_[1]);
	while (q--) {
		scanf("%d", &i), i--;
		a = aa[i], b = aa[i + 1];
		aa[i] = b, aa[i + 1] = a;
		if (i >= k - 1) {
			j = jj[a];
			update_(i - k + 1, max(j - k + 1, 0), -1);
			if (j + k < n)
				update_(i - k + 1, j + 1, 1);
			j = jj[b];
			update_(i - k + 1, max(j - k + 1, 0), 1);
			if (j + k < n)
				update_(i - k + 1, j + 1, -1);
		}
		if (i + k < n) {
			j = jj[a];
			update_(i + 1, max(j - k + 1, 0), 1);
			if (j + k < n)
				update_(i + 1, j + 1, -1);
			j = jj[b];
			update_(i + 1, max(j - k + 1, 0), -1);
			if (j + k < n)
				update_(i + 1, j + 1, 1);
		}
		printf("%d %lld\n", mx[1], kk_[1]);
	}
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:95:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |  scanf("%d%d%d", &n, &k, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:97:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |   scanf("%d", &aa[i]), aa[i]--;
      |   ^~~~~~~~~~~~~~~~~~~
Main.c:99:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |   scanf("%d", &a), a--;
      |   ^~~~~~~~~~~~~~~
Main.c:119:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |   scanf("%d", &i), i--;
      |   ^~~~~~~~~~~~~~~

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