Submission #666804

#	Time	Username	Problem	Language	Result	Execution time	Memory
666804		rainboy	Event Hopping 2 (JOI21_event2)	C11	100 / 100	282 ms	13716 KiB

event2

#include <stdio.h>

#define N	100000
#define H	17	/* H = ceil(log2(N)) */
#define INF	0x7fffffff

unsigned int Z = 12345;

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

int xx[N * 2], ii[N * 2], 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)
			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 zz[N + 1], ii_[N + 1], ll[N + 1], rr[N + 1], u_, l_, r_;

int node(int i) {
	static int _ = 1;

	zz[_] = rand_(), ii_[_] = i;
	return _++;
}

void split(int u, int i) {
	int c;

	if (u == 0) {
		u_ = l_ = r_ = 0;
		return;
	}
	c = xx[ii_[u] << 1 | 0] != xx[i << 1 | 0] ? xx[ii_[u] << 1 | 0] - xx[i << 1 | 0] : ii_[u] - i;
	if (c < 0) {
		split(rr[u], i);
		rr[u] = l_, l_ = u;
	} else if (c > 0) {
		split(ll[u], i);
		ll[u] = r_, r_ = u;
	} else {
		u_ = u, l_ = ll[u], r_ = rr[u];
		ll[u] = rr[u] = 0;
	}
}

int merge(int u, int v) {
	if (u == 0)
		return v;
	if (v == 0)
		return u;
	if (zz[u] < zz[v]) {
		rr[u] = merge(rr[u], v);
		return u;
	} else {
		ll[v] = merge(u, ll[v]);
		return v;
	}
}

int tr_lower(int i) {
	int u = u_, i_ = -1;

	while (u)
		if (xx[ii_[u] << 1 | 0] < xx[i << 1 | 0] || xx[ii_[u] << 1 | 0] == xx[i << 1 | 0] && ii_[u] < i)
			i_ = ii_[u], u = rr[u];
		else
			u = ll[u];
	return i_;
}

int tr_higher(int i) {
	int u = u_, i_ = -1;

	while (u)
		if (xx[ii_[u] << 1 | 0] > xx[i << 1 | 0] || xx[ii_[u] << 1 | 0] == xx[i << 1 | 0] && ii_[u] > i)
			i_ = ii_[u], u = ll[u];
		else
			u = rr[u];
	return i_;
}

void tr_add(int i) {
	split(u_, i);
	u_ = merge(merge(l_, node(i)), r_);
}

int ii1[N * 2 + 1], pp[H + 1][N];

int count(int l, int r) {
	int lower = -1, upper = n * 2, h, i, k;

	while (upper - lower > 1) {
		i = (lower + upper) / 2;
		if (xx[ii[i]] >= l)
			upper = i;
		else
			lower = i;
	}
	i = upper;
	if (ii1[i] == -1 || xx[ii1[i] << 1 | 1] > r)
		return 0;
	i = ii1[i];
	k = 1;
	for (h = H; h >= 0; h--)
		if (pp[h][i] != -1 && xx[pp[h][i] << 1 | 1] <= r)
			k += 1 << h, i = pp[h][i];
	return k;
}

int main() {
	int k, h, i, i_, p, q, l, r, k_, k1, k1_;

	scanf("%d%d", &n, &k);
	for (i = 0; i < n; i++) {
		scanf("%d%d", &xx[i << 1 | 0], &xx[i << 1 | 1]);
		xx[i << 1 | 0] = xx[i << 1 | 0] << 1 | 1, xx[i << 1 | 1] = xx[i << 1 | 1] << 1 | 0;
	}
	for (i = 0; i < n * 2; i++)
		ii[i] = i;
	sort(ii, 0, n * 2);
	ii1[n * 2] = -1;
	for (i = n * 2 - 1; i >= 0; i--) {
		i_ = ii[i];
		ii1[i] = ii1[i + 1];
		if ((i_ & 1) == 0) {
			if (ii1[i] == -1 || xx[ii1[i] << 1 | 1] > xx[i_ ^ 1])
				ii1[i] = i_ >> 1;
		} else
			pp[0][i_ >> 1] = ii1[i];
	}
	for (h = 1; h <= H; h++)
		for (i = 0; i < n; i++)
			pp[h][i] = pp[h - 1][i] == -1 ? -1 : pp[h - 1][pp[h - 1][i]];
	k1 = count(0, INF);
	if (k1 < k) {
		printf("-1\n");
		return 0;
	}
	for (i = 0, k_ = 0; i < n && k_ < k; i++) {
		p = tr_lower(i), q = tr_higher(i);
		l = p == -1 ? 0 : xx[p << 1 | 1], r = q == -1 ? INF : xx[q << 1 | 0];
		if (l <= xx[i << 1 | 0] && xx[i << 1 | 1] <= r) {
			k1_ = k1 - count(l, r) + count(l, xx[i << 1 | 0]) + count(xx[i << 1 | 1], r);
			if (k1_ + k_ + 1 >= k)
				printf("%d\n", i + 1), tr_add(i), k1 = k1_, k_++;
		}
	}
	return 0;
}

Compilation message (stderr)

event2.c: In function 'tr_lower':
event2.c:81:85: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   81 |   if (xx[ii_[u] << 1 | 0] < xx[i << 1 | 0] || xx[ii_[u] << 1 | 0] == xx[i << 1 | 0] && ii_[u] < i)
      |                                               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
event2.c: In function 'tr_higher':
event2.c:92:85: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   92 |   if (xx[ii_[u] << 1 | 0] > xx[i << 1 | 0] || xx[ii_[u] << 1 | 0] == xx[i << 1 | 0] && ii_[u] > i)
      |                                               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
event2.c: In function 'main':
event2.c:130:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |  scanf("%d%d", &n, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~
event2.c:132:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |   scanf("%d%d", &xx[i << 1 | 0], &xx[i << 1 | 1]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 1 / 1
• Subtask 3: 31 / 31
• Subtask 4: 61 / 61