제출 #666783

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
666783		rainboy	Event Hopping 2 (JOI21_event2)	C11	32 / 100	3055 ms	3932 KiB

event2

#include <stdio.h>

#define N	100000
#define INF	0x3f3f3f3f

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 count(int l, int r) {
	int i, i_, k;

	k = 0;
	for (i = 0; i < n * 2 && xx[i_ = ii[i]] <= r; i++)
		if ((i_ & 1) == 1)
			if (l <= xx[i_ ^ 1])
				l = xx[i_], k++;
	return k;
}

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

	scanf("%d%d", &n, &k);
	for (i = 0; i < n * 2; i++)
		scanf("%d", &xx[i]);
	for (i = 0; i < n * 2; i++)
		ii[i] = i;
	sort(ii, 0, n * 2);
	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;
}

컴파일 시 표준 에러 (stderr) 메시지

event2.c: In function 'tr_lower':
event2.c:80:85: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   80 |   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:91:85: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   91 |   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:117:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |  scanf("%d%d", &n, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~
event2.c:119:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |   scanf("%d", &xx[i]);
      |   ^~~~~~~~~~~~~~~~~~~

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