Submission #741192

#	Time	Username	Problem	Language	Result	Execution time	Memory
741192		rainboy	Interval Collection (CCO20_day2problem2)	C11	25 / 25	1166 ms	83140 KiB

Main

#include <stdio.h>

#define N	500000
#define N_	(1 << 20)	/* N_ = pow2(ceil(log2(N))) */
#define INF	0x3f3f3f3f

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

unsigned int Z = 12345;

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

char type[N]; int xx[N * 2], xx_[N * 2], prev[N];

int compare_lr(int i, int j) {
	if (xx[i << 1 | 0] != xx[j << 1 | 0])
		return xx[i << 1 | 0] - xx[j << 1 | 0];
	if (xx[i << 1 | 1] != xx[j << 1 | 1])
		return xx[i << 1 | 1] - xx[j << 1 | 1];
	return i - j;
}

int compare_x(int i, int j) {
	return xx[i] != xx[j] ? xx[i] - xx[j] : (j & 1) - (i & 1);
}

int (*compare)(int, int);

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 = compare(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 stl[N_ * 2], str[N_ * 2], stlr[N_ * 2];
int stl1[N_ * 2], str1[N_ * 2], stl2[N_ * 2], str2[N_ * 2];
int n_;

void build(int n) {
	int i;

	n_ = 1;
	while (n_ < n)
		n_ <<= 1;
	for (i = 1; i < n_ * 2; i++) {
		stl[i] = -INF, str[i] = INF, stlr[i] = INF;
		stl1[i] = -INF, str1[i] = INF, stl2[i] = -INF, str2[i] = INF;
	}
}

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

	stl[i] = max(stl[l], stl[r]);
	str[i] = min(str[l], str[r]);
	stlr[i] = min(stlr[l], stlr[r]);
	if (stl[l] != -INF && str[r] != INF)
		stlr[i] = min(stlr[i], str[r] - stl[l]);
}

void update1(int i, int l, int r) {
	i += n_;
	stl[i] = l, str[i] = r, stlr[i] = INF;
	while (i > 1)
		pul1(i >>= 1);
}

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

	if (stl1[l] > stl1[r] || stl1[l] == stl1[r] && str1[l] < str1[r])
		stl1[i] = stl1[l], str1[i] = str1[l];
	else
		stl1[i] = stl1[r], str1[i] = str1[r];
	if (str2[l] < str2[r] || str2[l] == str2[r] && stl2[l] > stl2[r])
		stl2[i] = stl2[l], str2[i] = str2[l];
	else
		stl2[i] = stl2[r], str2[i] = str2[r];
}

void update2(int i, int l, int r) {
	i += n_;
	stl1[i] = l, str1[i] = r, stl2[i] = l, str2[i] = r;
	while (i > 1)
		pul2(i >>= 1);
}

int main() {
	static int ii[N * 2], qu[N];
	int n, cnt, i, i_, j, l, r;

	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		static char s[2];

		scanf("%s%d%d", s, &xx[i << 1 | 0], &xx[i << 1 | 1]);
		type[i] = s[0] == 'A' ? 0 : 1;
	}
	for (i = 0; i < n; i++)
		ii[i] = i;
	compare = compare_lr, sort(ii, 0, n);
	for (i = 0; i < n; i = j) {
		l = xx[ii[i] << 1 | 0], r = xx[ii[i] << 1 | 1];
		j = i, cnt = 0;
		while (j < n && xx[ii[j] << 1 | 0] == l && xx[ii[j] << 1 | 1] == r) {
			i_ = ii[j++];
			if (type[i_] == 0)
				qu[cnt++] = i_;
			else
				prev[i_] = qu[--cnt];
		}
	}
	for (i = 0; i < n * 2; i++)
		ii[i] = i;
	compare = compare_x, sort(ii, 0, n * 2);
	for (i = 0; i < n * 2; i++)
		xx_[ii[i]] = i;
	build(n * 2);
	for (i = 0; i < n; i++) {
		if (type[i] == 0) {
			update1(xx_[i << 1 | 0], -INF, xx[i << 1 | 1]);
			update1(xx_[i << 1 | 1], xx[i << 1 | 0], INF);
			update2(xx_[i << 1 | 0], xx[i << 1 | 0], xx[i << 1 | 1]);
		} else {
			update1(xx_[prev[i] << 1 | 0], -INF, INF);
			update1(xx_[prev[i] << 1 | 1], -INF, INF);
			update2(xx_[prev[i] << 1 | 0], -INF, INF);
		}
		printf("%d\n", stlr[1] != INF ? stlr[1] : str1[1] - stl2[1]);
	}
	return 0;
}

Compilation message (stderr)

Main.c: In function 'pul2':
Main.c:90:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   90 |  if (stl1[l] > stl1[r] || stl1[l] == stl1[r] && str1[l] < str1[r])
      |                           ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
Main.c:94:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   94 |  if (str2[l] < str2[r] || str2[l] == str2[r] && stl2[l] > stl2[r])
      |                           ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
Main.c: In function 'main':
Main.c:111:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
Main.c:115:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |   scanf("%s%d%d", s, &xx[i << 1 | 0], &xx[i << 1 | 1]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 7 / 7
• Subtask 4: 4 / 4
• Subtask 5: 3 / 3