Submission #545461

#	Time	Username	Problem	Language	Result	Execution time	Memory
545461		rainboy	Fortune Telling 2 (JOI14_fortune_telling2)	C11	100 / 100	285 ms	16844 KiB

fortune_telling2

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

#define N	200000
#define M	200000
#define N1	(N * 2 + M)
#define N_	(1 << 18)	/* N_ = pow2(ceil(log2(M))) */

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

unsigned int X = 12345;

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

int xx[N1], yy[N1], tt[N];

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

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 st[N_ * 2], n_;

void build(int *aa, int n) {
	int i;

	n_ = 1;
	while (n_ < n)
		n_ <<= 1;
	memset(st, -1, n_ * 2 * sizeof *st);
	for (i = 0; i < n; i++)
		st[n_ + aa[i]] = max(st[n_ + aa[i]], i);
	for (i = n_ - 1; i > 0; i--)
		st[i] = max(st[i << 1 | 0], st[i << 1 | 1]);
}

int st_query(int l, int r) {
	int x = -1;

	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			x = max(x, st[l++]);
		if ((r & 1) == 0)
			x = max(x, st[r--]);
	}
	return x;
}

int ft[M];

void ft_update(int i, int n, int x) {
	while (i < n) {
		ft[i] += x;
		i |= i + 1;
	}
}

int ft_query(int i) {
	int x = 0;

	while (i >= 0) {
		x += ft[i];
		i &= i + 1, i--;
	}
	return x;
}

int main() {
	static int ii[N1];
	int n, n1, m, i, i_, j, l, r, x, y, tmp, flip;
	long long sum;

	scanf("%d%d", &n, &m), n1 = n * 2 + m;
	for (i = 0; i < n1; i++)
		scanf("%d", &xx[i]);
	for (i = 0; i < n1; i++)
		ii[i] = i;
	compare = compare_x, sort(ii, 0, n1);
	for (i = 0, x = 0, y = -1; i < n1; i++) {
		i_ = ii[i];
		if (i_ >= n * 2 && x != xx[i_])
			x = xx[i_], y++;
		yy[i_] = y;
	}
	build(yy + n * 2, m);
	for (i = 0; i < n; i++) {
		l = yy[i << 1 | 0], r = yy[i << 1 | 1];
		if (l > r)
			tmp = l, l = r, r = tmp;
		tt[i] = st_query(l + 1, r);
	}
	for (i = 0; i < n; i++)
		ii[i] = i;
	compare = compare_t, sort(ii, 0, n);
	sum = 0;
	for (i = 0, j = m - 1; i < n; i++) {
		i_ = ii[i];
		while (j > tt[i_])
			ft_update(m - 1 - yy[n * 2 + j--], m, 1);
		flip = 0;
		if (tt[i_] != -1 && xx[i_ << 1 | 0] < xx[i_ << 1 | 1])
			flip ^= 1;
		if (ft_query(m - 2 - yy[i_ << 1 | 0]) % 2 != 0)
			flip ^= 1;
		sum += xx[i_ << 1 | flip];
	}
	printf("%lld\n", sum);
	return 0;
}

Compilation message (stderr)

fortune_telling2.c: In function 'main':
fortune_telling2.c:97:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |  scanf("%d%d", &n, &m), n1 = n * 2 + m;
      |  ^~~~~~~~~~~~~~~~~~~~~
fortune_telling2.c:99:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |   scanf("%d", &xx[i]);
      |   ^~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65