Submission #709847

#	Time	Username	Problem	Language	Result	Execution time	Memory
709847		rainboy	Railway Trip 2 (JOI22_ho_t4)	C11	100 / 100	359 ms	56588 KiB

Main

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

#define N	100000
#define H	17	/* H = ceil(log2(N)) */
#define N_	(1 << H)
#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; }

int n, n_;

int stmn[N_ * 2], stmx[N_ * 2];

void build1() {
	int i;

	memset(stmn, 0x3f, n_ * 2 * sizeof *stmn);
	memset(stmx, -1, n_ * 2 * sizeof *stmx);
	for (i = 0; i < n; i++)
		stmn[n_ + i] = stmx[n_ + i] = i;
}

void update1(int l, int r, int x, int y) {
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			stmn[l] = min(stmn[l], x), stmx[l] = max(stmx[l], y), l++;
		if ((r & 1) == 0)
			stmn[r] = min(stmn[r], x), stmx[r] = max(stmx[r], y), r--;
	}
}

void push1() {
	int i;

	for (i = 0; i < n_; i++) {
		int l = i << 1, r = l | 1;

		stmn[l] = min(stmn[l], stmn[i]), stmx[l] = max(stmx[l], stmx[i]);
		stmn[r] = min(stmn[r], stmn[i]), stmx[r] = max(stmx[r], stmx[i]);
	}
}

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

	stmn[i] = min(stmn[l], stmn[r]);
	stmx[i] = max(stmx[l], stmx[r]);
}

void build2(int *stmn, int *stmx, int *ll, int *rr) {
	int i;

	for (i = 0; i < n_; i++)
		if (i < n)
			stmn[n_ + i] = ll[i], stmx[n_ + i] = rr[i];
		else
			stmn[n_ + i] = INF, stmx[n_ + i] = -1;
	for (i = n_ - 1; i > 0; i--)
		pul2(stmn, stmx, i);
}

void query2(int *stmn, int *stmx, int l, int r, int *l_, int *r_) {
	*l_ = INF, *r_ = -1;
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			*l_ = min(*l_, stmn[l]), *r_ = max(*r_, stmx[l]), l++;
		if ((r & 1) == 0)
			*l_ = min(*l_, stmn[r]), *r_ = max(*r_, stmx[r]), r--;
	}
}

int main() {
	static int stmn_[H + 1][N_ * 2], stmx_[H + 1][N_ * 2], ll[H + 1][N], rr[H + 1][N];
	int k, q, m, h, i, j;

	scanf("%d%d%d", &n, &k, &m);
	n_ = 1;
	while (n_ < n)
		n_ <<= 1;
	build1();
	while (m--) {
		scanf("%d%d", &i, &j), i--, j--;
		if (i < j)
			update1(i, min(i + k - 1, j - 1), INF, j);
		else
			update1(max(i - k + 1, j + 1), i, j, -1);
	}
	push1();
	for (h = 0; h <= H; h++) {
		if (h == 0)
			for (i = 0; i < n; i++)
				ll[0][i] = stmn[n_ + i], rr[0][i] = stmx[n_ + i];
		else
			for (i = 0; i < n; i++)
				query2(stmn_[h - 1], stmx_[h - 1], ll[h - 1][i], rr[h - 1][i], &ll[h][i], &rr[h][i]);
		build2(stmn_[h], stmx_[h], ll[h], rr[h]);
	}
	scanf("%d", &q);
	while (q--) {
		int l, r, l_, r_;

		scanf("%d%d", &i, &j), i--, j--;
		l = i, r = i;
		query2(stmn_[H], stmx_[H], l, r, &l_, &r_);
		if (j < l_ || j > r_) {
			printf("-1\n");
			continue;
		}
		k = 0;
		for (h = H; h >= 0; h--) {
			query2(stmn_[h], stmx_[h], l, r, &l_, &r_);
			if (j < l_ || j > r_)
				k += 1 << h, l = l_, r = r_;
		}
		printf("%d\n", k + 1);
	}
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:78:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |  scanf("%d%d%d", &n, &k, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:84:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~
Main.c:100:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
Main.c:104:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 11 / 11
• Subtask 4: 25 / 25
• Subtask 5: 35 / 35
• Subtask 6: 13 / 13