oj.uz

Submission #503243

# Submission time Handle Problem Language Result Execution time Memory
503243 2022-01-07T14:52:29 Z rainboy Osumnjičeni (COCI21_osumnjiceni) C
10 / 110
 1000 ms 5792 KB 
#include <stdio.h>
#include <string.h>

#define N	200000

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

unsigned int X = 12345;

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

int xx[N * 2];

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)
			if (xx[ii[j]] == xx[i_])
				j++;
			else if (xx[ii[j]] < xx[i_]) {
				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 main() {
	static int dd[N * 2], jj[N];
	int n, q, i, j;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d%d", &xx[i << 1 | 0], &xx[i << 1 | 1]), xx[i << 1 | 1]++;
	scanf("%d", &q);
	for (i = 0; i < n; i++) {
		for (j = i + 1; j < n; j++)
			if (max(xx[i << 1 | 0], xx[j << 1 | 0]) < min(xx[i << 1 | 1], xx[j << 1 | 1]))
				break;
		jj[i] = j;
	}
	for (i = n - 2; i >= 0; i--)
		jj[i] = min(jj[i], jj[i + 1]);
	while (q--) {
		int k;

		scanf("%d%d", &i, &j), i--, j--;
		memset(dd, 0, n * 2 * sizeof *dd);
		k = 0;
		while (i <= j)
			i = jj[i], k++;
		printf("%d\n", k);
	}
	return 0;
}

Compilation message

Main.c: In function 'main':
Main.c:40:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
Main.c:42:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |   scanf("%d%d", &xx[i << 1 | 0], &xx[i << 1 | 1]), xx[i << 1 | 1]++;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:43:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
Main.c:55:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 4164 KB Output is correct
2 Correct 48 ms 4164 KB Output is correct
3 Correct 50 ms 4224 KB Output is correct
4 Correct 50 ms 4228 KB Output is correct
5 Correct 57 ms 4424 KB Output is correct
6 Correct 48 ms 4076 KB Output is correct
7 Correct 48 ms 4172 KB Output is correct
8 Correct 57 ms 4148 KB Output is correct
9 Correct 54 ms 4288 KB Output is correct
10 Correct 53 ms 4148 KB Output is correct
11 Execution timed out 1004 ms 2224 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 324 KB Output is correct
2 Correct 18 ms 344 KB Output is correct
3 Correct 17 ms 332 KB Output is correct
4 Correct 21 ms 412 KB Output is correct
5 Correct 19 ms 404 KB Output is correct
6 Correct 25 ms 332 KB Output is correct
7 Correct 19 ms 332 KB Output is correct
8 Correct 17 ms 416 KB Output is correct
9 Correct 16 ms 332 KB Output is correct
10 Correct 11 ms 416 KB Output is correct
11 Correct 24 ms 412 KB Output is correct
12 Correct 22 ms 404 KB Output is correct
13 Correct 24 ms 332 KB Output is correct
14 Correct 23 ms 396 KB Output is correct
15 Correct 25 ms 336 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 54 ms 408 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 324 KB Output is correct
2 Correct 18 ms 344 KB Output is correct
3 Correct 17 ms 332 KB Output is correct
4 Correct 21 ms 412 KB Output is correct
5 Correct 19 ms 404 KB Output is correct
6 Correct 25 ms 332 KB Output is correct
7 Correct 19 ms 332 KB Output is correct
8 Correct 17 ms 416 KB Output is correct
9 Correct 16 ms 332 KB Output is correct
10 Correct 11 ms 416 KB Output is correct
11 Correct 24 ms 412 KB Output is correct
12 Correct 22 ms 404 KB Output is correct
13 Correct 24 ms 332 KB Output is correct
14 Correct 23 ms 396 KB Output is correct
15 Correct 25 ms 336 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 54 ms 408 KB Output is correct
18 Correct 698 ms 1396 KB Output is correct
19 Correct 623 ms 1368 KB Output is correct
20 Correct 720 ms 1488 KB Output is correct
21 Correct 619 ms 1276 KB Output is correct
22 Correct 651 ms 1408 KB Output is correct
23 Correct 770 ms 1248 KB Output is correct
24 Correct 647 ms 1312 KB Output is correct
25 Correct 554 ms 1592 KB Output is correct
26 Correct 465 ms 1316 KB Output is correct
27 Correct 376 ms 1304 KB Output is correct
28 Correct 219 ms 964 KB Output is correct
29 Correct 241 ms 796 KB Output is correct
30 Correct 225 ms 844 KB Output is correct
31 Correct 237 ms 892 KB Output is correct
32 Correct 230 ms 900 KB Output is correct
33 Correct 0 ms 204 KB Output is correct
34 Execution timed out 1046 ms 1016 KB Time limit exceeded

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 4308 KB Output is correct
2 Correct 64 ms 4368 KB Output is correct
3 Correct 61 ms 4116 KB Output is correct
4 Correct 59 ms 4016 KB Output is correct
5 Correct 60 ms 4196 KB Output is correct
6 Correct 63 ms 4652 KB Output is correct
7 Correct 61 ms 4312 KB Output is correct
8 Correct 63 ms 5792 KB Output is correct
9 Correct 57 ms 5764 KB Output is correct
10 Correct 62 ms 5740 KB Output is correct
11 Execution timed out 1089 ms 1988 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 4164 KB Output is correct
2 Correct 48 ms 4164 KB Output is correct
3 Correct 50 ms 4224 KB Output is correct
4 Correct 50 ms 4228 KB Output is correct
5 Correct 57 ms 4424 KB Output is correct
6 Correct 48 ms 4076 KB Output is correct
7 Correct 48 ms 4172 KB Output is correct
8 Correct 57 ms 4148 KB Output is correct
9 Correct 54 ms 4288 KB Output is correct
10 Correct 53 ms 4148 KB Output is correct
11 Execution timed out 1004 ms 2224 KB Time limit exceeded
12 Halted 0 ms 0 KB -