Submission #470006

#	Time	Username	Problem	Language	Result	Execution time	Memory
470006		rainboy	Plahte (COCI17_plahte)	C11	160 / 160	389 ms	21764 KiB

plahte

#include <stdio.h>
#include <stdlib.h>

#define N	80000
#define M	80000
#define N_	(N + M)
#define K	(N * 2 + M)

unsigned int X = 12345;

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

int xx[N_ * 2], yy[N_ * 2], n, m, n_, k;
int ta[N], tb[N], cc[M], cc_[M], m_;

int compare_x(int i, int j) {
	int ti, tj;

	if (xx[i] != xx[j])
		return xx[i] - xx[j];
	ti = i >= n * 2 ? 0 : ((i & 1) == 0 ? 1 : -1), tj = j >= n * 2 ? 0 : ((j & 1) == 0 ? 1 : -1);
	return tj - ti;
}

int compare_c_(int i, int j) {
	return cc_[i] != cc_[j] ? cc_[i] - cc_[j] : i - j;
}

int compare_tb(int i, int j) {
	return tb[i] - tb[j];
}

int (*compare)(int, int);

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) {
			int c = compare(ii[j], i_);

			if (c == 0)
				j++;
			else if (c < 0) {
				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[1 + N * 2], ll[1 + N * 2], rr[1 + N * 2], ii[1 + N * 2], u_, l_, r_;

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

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

void split(int u, int y) {
	if (u == 0) {
		u_ = l_ = r_ = 0;
		return;
	}
	if (yy[ii[u]] < y) {
		split(rr[u], y);
		rr[u] = l_, l_ = u;
	} else if (yy[ii[u]] > y) {
		split(ll[u], y);
		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 last(int u) {
	return rr[u] == 0 ? u : last(rr[u]);
}

int pp[N_], *ej[N_], eo[N_];

void append(int i, int j) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
	ej[i][o] = j;
}

void sweep() {
	static int hh[K];
	int h, h_, i, j;

	for (h = 0; h < k; h++)
		hh[h] = h;
	compare = compare_x, sort(hh, 0, k);
	for (i = 0; i < n_; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (h = 0; h < k; h++) {
		int p, l, r;

		h_ = hh[h];
		if (h_ >= n * 2) {
			j = h_ - n * 2;
			split(u_, yy[h_]);
			if (u_)
				pp[n + j] = ii[u_] >> 1;
			else {
				p = l_ == 0 ? -1 : ii[last(l_)];
				pp[n + j] = p == -1 ? -1 : ((p & 1) == 0 ? p >> 1 : pp[p >> 1]);
			}
			u_ = merge(merge(l_, u_), r_);
		} else {
			i = h_ >> 1;
			if ((h_ & 1) == 0) {
				split(u_, yy[i << 1 | 0]);
				p = l_ == 0 ? -1 : ii[last(l_)];
				pp[i] = p == -1 ? -1 : ((p & 1) == 0 ? p >> 1 : pp[p >> 1]);
				u_ = merge(merge(l_, merge(node(i << 1 | 0), node(i << 1 | 1))), r_);
			} else {
				split(u_, yy[i << 1 | 0]), l = l_, split(r_, yy[i << 1 | 1]), r = r_;
				u_ = merge(l, r);
			}
		}
	}
	for (i = 0; i < n_; i++)
		if (pp[i] != -1)
			append(pp[i], i);
}

void dfs(int i) {
	int o;

	if (i >= n)
		cc_[m_++] = cc[i - n];
	else {
		ta[i] = m_;
		for (o = eo[i]; o--; ) {
			int j = ej[i][o];

			dfs(j);
		}
		tb[i] = m_;
	}
}

int ft[M];

void update(int i, int n, int x) {
	while (i < n) {
		ft[i] += x;
		i |= i + 1;
	}
}

int query(int i) {
	int x = 0;

	while (i >= 0) {
		x += ft[i];
		i &= i + 1, i--;
	}
	return x;
}

void solve() {
	static int ii[N], jj[M], prev[M], ans[N];
	int i, j;

	for (j = 0; j < m; j++)
		jj[j] = j;
	compare = compare_c_, sort(jj, 0, m);
	for (j = 0; j < m; j++)
		prev[jj[j]] = j == 0 || cc_[jj[j]] != cc_[jj[j - 1]] ? -1 : jj[j - 1];
	for (i = 0; i < n; i++)
		ii[i] = i;
	compare = compare_tb, sort(ii, 0, n);
	for (i = 0, j = 0; i < n; i++) {
		int i_ = ii[i];

		while (j < tb[i_]) {
			update(j, m, 1);
			if (prev[j] != -1)
				update(prev[j], m, -1);
			j++;
		}
		ans[i_] = query(tb[i_] - 1) - query(ta[i_] - 1);
	}
	for (i = 0; i < n; i++)
		printf("%d\n", ans[i]);
}

int main() {
	int i, j;

	scanf("%d%d", &n, &m), n_ = n + m, k = n * 2 + m;
	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]);
	for (j = 0; j < m; j++)
		scanf("%d%d%d", &xx[n * 2 + j], &yy[n * 2 + j], &cc[j]);
	sweep();
	for (i = 0; i < n_; i++)
		if (pp[i] == -1)
			dfs(i);
	solve();
	return 0;
}

Compilation message (stderr)

plahte.c: In function 'append':
plahte.c:109:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
  109 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
plahte.c: In function 'main':
plahte.c:220:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  220 |  scanf("%d%d", &n, &m), n_ = n + m, k = n * 2 + m;
      |  ^~~~~~~~~~~~~~~~~~~~~
plahte.c:222:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  222 |   scanf("%d%d%d%d", &xx[i << 1 | 0], &yy[i << 1 | 0], &xx[i << 1 | 1], &yy[i << 1 | 1]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plahte.c:224:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  224 |   scanf("%d%d%d", &xx[n * 2 + j], &yy[n * 2 + j], &cc[j]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 32 / 32
• Subtask 2: 32 / 32
• Subtask 3: 32 / 32
• Subtask 4: 32 / 32
• Subtask 5: 32 / 32