oj.uz

Submission #484587

# Submission time Handle Problem Language Result Execution time Memory
484587 2021-11-04T14:06:39 Z rainboy Index (COCI21_index) C
110 / 110
 2005 ms 51496 KB 
#include <stdio.h>

#define N	200000
#define LN	18	/* LN = ceil(log2(N)) */
#define N_	(1 + N * (LN + 1))

unsigned int X = 12345;

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

int aa[N];

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k) {
			int c = aa[ii[j]] - aa[i_];

			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		}
		sort(ii, l, i);
		l = k;
	}
}

int ll[N_], rr[N_], kk[N_], _;

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

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

		if (i < m)
			ll[t_] = update(ll[t], l, m, i), rr[t_] = rr[t];
		else
			ll[t_] = ll[t], rr[t_] = update(rr[t], m, r, i);
	}
	return t_;
}

int query(int t, int l, int r, int ql, int qr) {
	int m;

	if (qr <= l || r <= ql || t == 0)
		return 0;
	if (ql <= l && r <= qr)
		return kk[t];
	m = (l + r) / 2;
	return query(ll[t], l, m, ql, qr) + query(rr[t], m, r, ql, qr);
}

int main() {
	static int ii[N], tt[N + 1];
	int n, q, i, a, t;

	scanf("%d%d", &n, &q);
	for (i = 0; i < n; i++) {
		scanf("%d", &aa[i]);
		ii[i] = i;
	}
	sort(ii, 0, n);
	for (a = n, i = n - 1, t = 0; a >= 0; a--) {
		while (i >= 0 && aa[ii[i]] >= a)
			t = update(t, 0, n, ii[i--]);
		tt[a] = t;
	}
	while (q--) {
		int l, r, lower, upper;

		scanf("%d%d", &l, &r), l--;
		lower = 1, upper = r - l + 1;
		while (upper - lower > 1) {
			int a = (lower + upper) / 2;

			if (query(tt[a], 0, n, l, r) >= a)
				lower = a;
			else
				upper = a;
		}
		printf("%d\n", lower);
	}
	return 0;
}

Compilation message

index.c: In function 'main':
index.c:69:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |  scanf("%d%d", &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~
index.c:71:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
index.c:83:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |   scanf("%d%d", &l, &r), l--;
      |   ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 420 KB Output is correct
7 Correct 3 ms 460 KB Output is correct
8 Correct 2 ms 424 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 460 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 420 KB Output is correct
7 Correct 3 ms 460 KB Output is correct
8 Correct 2 ms 424 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 239 ms 11748 KB Output is correct
12 Correct 333 ms 11924 KB Output is correct
13 Correct 233 ms 11712 KB Output is correct
14 Correct 239 ms 11692 KB Output is correct
15 Correct 253 ms 11704 KB Output is correct
16 Correct 229 ms 11788 KB Output is correct
17 Correct 262 ms 11840 KB Output is correct
18 Correct 243 ms 11796 KB Output is correct
19 Correct 232 ms 11752 KB Output is correct
20 Correct 251 ms 11720 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 420 KB Output is correct
7 Correct 3 ms 460 KB Output is correct
8 Correct 2 ms 424 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 239 ms 11748 KB Output is correct
12 Correct 333 ms 11924 KB Output is correct
13 Correct 233 ms 11712 KB Output is correct
14 Correct 239 ms 11692 KB Output is correct
15 Correct 253 ms 11704 KB Output is correct
16 Correct 229 ms 11788 KB Output is correct
17 Correct 262 ms 11840 KB Output is correct
18 Correct 243 ms 11796 KB Output is correct
19 Correct 232 ms 11752 KB Output is correct
20 Correct 251 ms 11720 KB Output is correct
21 Correct 1888 ms 51396 KB Output is correct
22 Correct 1874 ms 51496 KB Output is correct
23 Correct 1948 ms 51420 KB Output is correct
24 Correct 1937 ms 51376 KB Output is correct
25 Correct 1893 ms 51332 KB Output is correct
26 Correct 1854 ms 51372 KB Output is correct
27 Correct 1945 ms 51400 KB Output is correct
28 Correct 2005 ms 51472 KB Output is correct
29 Correct 1907 ms 51388 KB Output is correct
30 Correct 1901 ms 51316 KB Output is correct