Submission #745257

#	Time	Username	Problem	Language	Result	Execution time	Memory
745257		rainboy	RMQ (NOI17_rmq)	C11	100 / 100	36 ms	4788 KiB

rmq

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

#define N	100000
#define Q	100000

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

unsigned int X = 12345;

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

int n;

int ll[Q], rr[Q], bb[Q];

void sort(int *hh, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (bb[hh[j]] == bb[h])
				j++;
			else if (bb[hh[j]] > bb[h]) {
				tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
			}
		sort(hh, l, i);
		l = k;
	}
}

int ds[N], jj[N]; char marked[N];

int find(int i) {
	return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}

void join(int i, int j) {
	i = find(i);
	j = find(j);
	if (i == j)
		return;
	if (ds[i] > ds[j])
		ds[i] = j;
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i, jj[i] = jj[j];
	}
}

int next(int i) {
	return !marked[i] ? i : jj[find(i)] + 1;
}

void mark(int i) {
	marked[i] = 1;
	if (i > 0 && marked[i - 1])
		join(i - 1, i);
	if (i + 1 < n && marked[i + 1])
		join(i, i + 1);
}

int main() {
	static int hh[Q], qu[N], aa[N];
	int q, cnt, h, h_, i, a, l, r;

	scanf("%d%d", &n, &q);
	for (h = 0; h < q; h++)
		scanf("%d%d%d", &ll[h], &rr[h], &bb[h]);
	for (h = 0; h < q; h++)
		hh[h] = h;
	sort(hh, 0, q);
	memset(ds, -1, n * sizeof *ds);
	for (i = 0; i < n; i++)
		jj[i] = i;
	cnt = 0;
	for (a = n - 1, h = 0; a >= 0; a--) {
		h_ = h, l = 0, r = n - 1;
		while (h_ < q && bb[hh[h_]] == a)
			l = max(l, ll[hh[h_]]), r = min(r, rr[hh[h_]]), h_++;
		qu[cnt++] = a;
		if (h < h_) {
			if ((i = next(l)) > r) {
				for (i = 0; i < n; i++)
					printf("-1%c", i + 1 < n ? ' ' : '\n');
				return 0;
			}
			aa[i] = qu[--cnt], mark(i);
			while (h < h_) {
				l = ll[hh[h]], r = rr[hh[h]];
				while ((i = next(l)) <= r) {
					if (cnt == 0) {
						for (i = 0; i < n; i++)
							printf("-1%c", i + 1 < n ? ' ' : '\n');
						return 0;
					}
					aa[i] = qu[--cnt], mark(i);
				}
				h++;
			}
		}
	}
	while ((i = next(0)) < n)
		aa[i] = qu[--cnt], mark(i);
	for (i = 0; i < n; i++)
		printf("%d%c", aa[i], i + 1 < n ? ' ' : '\n');
	return 0;
}

Compilation message (stderr)

rmq.c: In function 'main':
rmq.c:75:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |  scanf("%d%d", &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~
rmq.c:77:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |   scanf("%d%d%d", &ll[h], &rr[h], &bb[h]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 23 / 23
• Subtask 2: 44 / 44
• Subtask 3: 33 / 33