Submission #439814

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
439814	2021-06-30T20:49:38 Z	rainboy	Kralj (COCI16_kralj)	C	140 / 140	1470 ms	30700 KB

kralj

#include <stdio.h>
#include <string.h>

#define N	500000

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int aa[N], bb[N];

int zz[1 + N], ll[1 + N], rr[1 + N], ii[1 + N], u_, l_, r_;

int node(int i) {
	static int _ = 1;

	zz[_] = rand_();
	ii[_] = i;
	return _++;
}

void split(int u, int i) {
	int c;

	if (u == 0) {
		u_ = l_ = r_ = 0;
		return;
	}
	c = bb[ii[u]] != bb[i] ? bb[ii[u]] - bb[i] : ii[u] - i;
	if (c < 0) {
		split(rr[u], i);
		rr[u] = l_, l_ = u;
	} else if (c > 0) {
		split(ll[u], i);
		ll[u] = r_, r_ = u;
	} else {
		u_ = u, l_ = ll[u], r_ = rr[u];
		ll[u] = rr[u] = 0;
	}
}

int merge(int u, int v) {
	if (u == 0)
		return v;
	if (v == 0)
		return u;
	if (zz[u] < zz[v]) {
		rr[u] = merge(rr[u], v);
		return u;
	} else {
		ll[v] = merge(u, ll[v]);
		return v;
	}
}

void tr_add(int i) {
	split(u_, i), u_ = merge(merge(l_, node(i)), r_);
}

void tr_remove(int i) {
	split(u_, i), u_ = merge(l_, r_);
}

int tr_first() {
	int u = u_;
	
	while (ll[u])
		u = ll[u];
	return ii[u];
}

int tr_higher(int a) {
	int u = u_, i = -1;
	
	while (u)
		if (bb[ii[u]] > a)
			i = ii[u], u = ll[u];
		else
			u = rr[u];
	return i;
}

int main() {
	static int kk[N + 1], pp[N], ii[N];
	int n, h, i, i_, k, cnt;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d", &pp[i]), pp[i]--, kk[pp[i]]++;
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]);
	for (i = 0; i < n; i++)
		scanf("%d", &bb[i]);
	k = 0, i_ = -1;
	for (i = 0; i < n; i++) {
		k += kk[i];
		if (k == 0)
			i_ = i;
		else
			k--;
	}
	memset(kk, 0, (n + 1) * sizeof *kk);
	for (i = 0; i < n; i++)
		kk[(pp[i] = (pp[i] - i_ + n - 1) % n) + 1]++;
	for (i = 1; i < n; i++)
		kk[i] += kk[i - 1];
	for (i = 0; i < n; i++)
		ii[kk[pp[i]]++] = i;
	cnt = 0;
	for (i = 0, h = 0; i < n; i++) {
		int j;

		while (h < n && pp[ii[h]] == i)
			tr_add(ii[h++]);
		j = tr_higher(aa[(i + i_ + 1) % n]);
		if (j != -1)
			cnt++;
		else
			j = tr_first();
		tr_remove(j);
	}
	printf("%d\n", cnt);
	return 0;
}

Compilation message

kralj.c: In function 'main':
kralj.c:89:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
kralj.c:91:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |   scanf("%d", &pp[i]), pp[i]--, kk[pp[i]]++;
      |   ^~~~~~~~~~~~~~~~~~~
kralj.c:93:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
kralj.c:95:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |   scanf("%d", &bb[i]);
      |   ^~~~~~~~~~~~~~~~~~~

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1470 ms	22944 KB	Output is correct
2	Correct	900 ms	22012 KB	Output is correct
3	Correct	1395 ms	27348 KB	Output is correct
4	Correct	1183 ms	27556 KB	Output is correct
5	Correct	777 ms	27948 KB	Output is correct
6	Correct	420 ms	27376 KB	Output is correct
7	Correct	654 ms	29036 KB	Output is correct
8	Correct	480 ms	26112 KB	Output is correct
9	Correct	671 ms	30700 KB	Output is correct
10	Correct	587 ms	29776 KB	Output is correct