oj.uz

답안 #827531

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
827531 2023-08-16T14:24:42 Z rainboy Sum Zero (RMI20_sumzero) C
100 / 100
 276 ms 19404 KB 
#include <stdio.h>

#define N	400000

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

unsigned int X = 12345;

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

long long aa[N + 1];

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_] ? (aa[ii[j]] < aa[i_] ? -1 : 1) : ii[j] - 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 main() {
	static int ii[N + 1], jj[N + 2], jj_[N + 2], dd[N + 2];
	static char rank[N + 2];
	int n, q, i, j, k;

	scanf("%d", &n);
	for (i = 1; i <= n; i++)
		scanf("%lld", &aa[i]), aa[i] += aa[i - 1];
	for (i = 0; i <= n; i++)
		ii[i] = i;
	sort(ii, 0, n + 1);
	jj[n + 1] = jj_[n + 1] = n + 1, dd[n + 1] = 0, rank[n + 1] = -1;
	for (i = 0; i <= n; i++)
		jj[ii[i]] = i == n || aa[ii[i + 1]] != aa[ii[i]] ? n + 1 : ii[i + 1];
	for (i = n; i >= 0; i--) {
		jj[i] = min(jj[i], jj[i + 1]);
		if (jj[i] == n + 1 || rank[jj[i]] != rank[jj_[jj[i]]])
			jj_[i] = jj[i], rank[i] = -1;
		else
			jj_[i] = jj_[jj_[jj[i]]], rank[i] = rank[jj[i]] + 1;
		dd[i] = dd[jj[i]] + 1;
	}
	scanf("%d", &q);
	while (q--) {
		scanf("%d%d", &i, &j), i--;
		k = i;
		while (jj[k] <= j)
			k = jj_[k] <= j ? jj_[k] : jj[k];
		printf("%d\n", dd[i] - dd[k]);
	}
	return 0;
}

Compilation message

sumzero.c: In function 'main':
sumzero.c:42:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
sumzero.c:44:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |   scanf("%lld", &aa[i]), aa[i] += aa[i - 1];
      |   ^~~~~~~~~~~~~~~~~~~~~
sumzero.c:59:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
sumzero.c:61:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |   scanf("%d%d", &i, &j), i--;
      |   ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 432 KB Output is correct
2 Correct 2 ms 520 KB Output is correct
3 Correct 3 ms 508 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 3 ms 468 KB Output is correct

Subtask #2
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 432 KB Output is correct
2 Correct 2 ms 520 KB Output is correct
3 Correct 3 ms 508 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 50 ms 3684 KB Output is correct
8 Correct 50 ms 3612 KB Output is correct
9 Correct 66 ms 3852 KB Output is correct
10 Correct 50 ms 3628 KB Output is correct
11 Correct 49 ms 3596 KB Output is correct
12 Correct 58 ms 3692 KB Output is correct

Subtask #3
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 432 KB Output is correct
2 Correct 2 ms 520 KB Output is correct
3 Correct 3 ms 508 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 50 ms 3684 KB Output is correct
8 Correct 50 ms 3612 KB Output is correct
9 Correct 66 ms 3852 KB Output is correct
10 Correct 50 ms 3628 KB Output is correct
11 Correct 49 ms 3596 KB Output is correct
12 Correct 58 ms 3692 KB Output is correct
13 Correct 241 ms 12572 KB Output is correct
14 Correct 225 ms 19228 KB Output is correct
15 Correct 272 ms 19172 KB Output is correct
16 Correct 225 ms 18252 KB Output is correct
17 Correct 225 ms 19152 KB Output is correct
18 Correct 276 ms 19404 KB Output is correct