Submission #477103

#	Time	Username	Problem	Language	Result	Execution time	Memory
477103		rainboy	Sunčanje (COCI18_suncanje)	C11	0 / 130	1058 ms	9720 KiB

suncanje

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

#define N	100000
#define N_	(1 << 18)	/* N_ = pow2(ceil(log2(N * 2))) */

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

unsigned int X = 12345;

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

int *zz;

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 (zz[ii[j]] == zz[i_])
				j++;
			else if (zz[ii[j]] < zz[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;
	}
}

void compress(int *xx, int n) {
	static int ii[N * 2];
	int i, x;

	for (i = 0; i < n; i++)
		ii[i] = i;
	zz = xx, sort(ii, 0, n);
	for (i = 0, x = 0; i < n; i++)
		xx[ii[i]] = i + 1 == n || xx[ii[i + 1]] != xx[ii[i]] ? x++ : x;
}

int st[N_ * 2], lz[N_], h_, n_;

void put(int i, int x) {
	st[i] = max(st[i], x);
	if (i < n_)
		lz[i] = max(lz[i], x);
}

void pus(int i) {
	if (lz[i] != -1)
		put(i << 1 | 0, lz[i]), put(i << 1 | 1, lz[i]), lz[i] = -1;
}

void pul(int i) {
	if (lz[i] == -1)
		st[i] = max(st[i << 1 | 0], st[i << 1 | 1]);
}

void push(int i) {
	int h;

	for (h = h_; h > 0; h--)
		pus(i >> h);
}

void pull(int i) {
	while (i > 1)
		pul(i >>= 1);
}

void update(int l, int r, int x) {
	int l_ = l += n_, r_ = r += n_;

	push(l_), push(r_);
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			put(l++, x);
		if ((r & 1) == 0)
			put(r--, x);
	}
	pull(l_), pull(r_);
}

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

	push(l += n_), push(r += n_);
	for ( ; 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;
}

void clean(int i) {
	if (st[i] == -1)
		return;
	st[i] = -1;
	if (i < n_)
		lz[i] = -1, clean(i << 1 | 0), clean(i << 1 | 1);
}

int xx[N * 2], yy[N * 2], mx[N];

void solve(int *ii, int n, int xl, int xr) {
	int i, i1, i2, i3, tmp;

	i1 = 0, i2 = 0, i3 = n;
	while (i2 < i3)
		if (xx[ii[i2] << 1 | 0] <= xl && xr <= xx[ii[i2] << 1 | 1])
			i2++;
		else if (xx[ii[i2] << 1 | 1] >= xl && xr >= xx[ii[i2] << 1 | 0]) {
			tmp = ii[i1], ii[i1] = ii[i2], ii[i2] = tmp;
			i1++, i2++;
		} else {
			i3--;
			tmp = ii[i2], ii[i2] = ii[i3], ii[i3] = tmp;
		}
	for (i = i1; i < i2; i++)
		update(yy[ii[i] << 1 | 0], yy[ii[i] << 1 | 1] - 1, ii[i]);
	for (i = 0; i < i2; i++)
		mx[ii[i]] = max(mx[ii[i]], query(yy[ii[i] << 1 | 0], yy[ii[i] << 1 | 1] - 1));
	clean(1);
	if (xr - xl > 1) {
		int xm = (xl + xr) / 2;

		solve(ii, i1, xl, xm), solve(ii, i1, xm, xr);
	}
}

int main() {
	static int ii[N];
	int n, i;

	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d%d%d%d", &xx[i << 1 | 0], &yy[i << 1 | 0], &xx[i << 1 | 1], &yy[i << 1 | 1]);
		xx[i << 1 | 1] += xx[i << 1 | 0], yy[i << 1 | 1] += yy[i << 1 | 0];
	}
	compress(xx, n * 2);
	compress(yy, n * 2);
	for (i = 0; i < n; i++)
		ii[i] = i;
	h_ = 0;
	while (1 << h_ < n * 2)
		h_++;
	n_ = 1 << h_;
	memset(st, -1, n_ * 2 * sizeof *st), memset(lz, -1, n_ * sizeof *lz);
	memset(mx, -1, n * sizeof *mx);
	solve(ii, n, 0, n * 2);
	for (i = 0; i < n; i++)
		printf(mx[i] <= i ? "DA\n" : "NE\n");
	return 0;
}

Compilation message (stderr)

suncanje.c: In function 'main':
suncanje.c:143:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
suncanje.c:145:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |   scanf("%d%d%d%d", &xx[i << 1 | 0], &yy[i << 1 | 0], &xx[i << 1 | 1], &yy[i << 1 | 1]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 13
• Subtask 3: 0 / 13
• Subtask 4: 0 / 13
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13
• Subtask 9: 0 / 13
• Subtask 10: 0 / 13