Submission #887624

#	Time	Username	Problem	Language	Result	Execution time	Memory
887624		rainboy	Iqea (innopolis2018_final_C)	C11	100 / 100	127 ms	37200 KiB

C

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

#define N	300000
#define M	300000
#define INF	0x3f3f3f3f

int abs_(int a) { return a > 0 ? a : -a; }
int min(int a, int b) { return a < b ? a : b; }

unsigned int X = 12345;

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

int xx[N], yy[N], xx_[N], yy_[N], n;
int tt[M], ii[M], ans[M], m;

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 = xx[ii[j]] != xx[i_] ? xx[ii[j]] - xx[i_] : yy[ii[j]] - yy[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 ll[N], rr[N], *ej[N], eo[N], 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 delete_(int i, int j) {
	int o;

	for (o = eo[i]; o--; )
		if (ej[i][o] == j) {
			eo[i]--;
			while (o < eo[i])
				ej[i][o] = ej[i][o + 1], o++;
			return;
		}
}

int sz[N], c;

void dfs1(int p, int i) {
	int o, centroid;

	sz[i] = 1, centroid = 1;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p) {
			dfs1(i, j);
			if (sz[j] * 2 > n_)
				centroid = 0;
			sz[i] += sz[j];
		}
	}
	if ((n_ - sz[i]) * 2 > n_)
		centroid = 0;
	if (centroid)
		c = i;
}

int ii_[N], dd[N], oo[N];

void dfs2(int p, int i, int o_) {
	int o, p_, i_, y;

	if (p == -1)
		for (i_ = ll[i]; i_ <= rr[i]; i_++)
			ii_[i_] = i_ - ll[i], dd[i_] = 0;
	else
		for (i_ = ll[i]; i_ <= rr[i]; i_++) {
			y = yy[i_];
			if (y < yy[ll[p]])
				p_ = ll[p];
			else if (y > yy[rr[p]])
				p_ = rr[p];
			else
				p_ = ll[p] + y - yy[ll[p]];
			ii_[i_] = ii_[p_], dd[i_] = dd[p_] + 1 + abs_(y - yy[p_]);
		}
	for (i_ = ll[i]; i_ <= rr[i]; i_++)
		oo[i_] = o_;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p)
			dfs2(i, j, p == -1 ? o : o_);
	}
}

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

int query(int *ft, int i) {
	int x = INF;

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

void cd(int *hh, int m, int n, int i) {
	static int ft1[N], ft2[N], kk[N], hh_[M];
	int m_, o, h, h_, i_, d, d_;

	n_ = n, dfs1(-1, i), i = c;
	dfs2(-1, i, -1);
	memset(ft1, 0x3f, (rr[i] - ll[i] + 1) * sizeof *ft1);
	memset(ft2, 0x3f, (rr[i] - ll[i] + 1) * sizeof *ft2);
	for (h = 0; h < m; h++) {
		h_ = hh[h], i_ = ii_[ii[h_]], d = dd[ii[h_]];
		if (tt[h_] == 1)
			update(ft1, i_, rr[i] - ll[i] + 1, d - i_), update(ft2, rr[i] - ll[i] - i_, rr[i] - ll[i] + 1, d + i_);
		else {
			if ((d_ = query(ft1, i_)) != INF)
				ans[h_] = min(ans[h_], d + d_ + i_);
			if ((d_ = query(ft2, rr[i] - ll[i] - i_)) != INF)
				ans[h_] = min(ans[h_], d + d_ - i_);
		}
	}
	memset(kk, 0, (eo[i] + 1) * sizeof *kk);
	for (h = 0; h < m; h++) {
		h_ = hh[h], o = oo[ii[h_]];
		if (o != -1)
			kk[o + 1]++;
	}
	for (o = 1; o < eo[i]; o++)
		kk[o] += kk[o - 1];
	m_ = 0;
	for (h = 0; h < m; h++) {
		h_ = hh[h], o = oo[ii[h_]];
		if (o != -1)
			hh_[kk[o]++] = h_, m_++;
	}
	memcpy(hh, hh_, (m = m_) * sizeof *hh_);
	for (o = 0, h = 0; o < eo[i]; o++, h = h_) {
		int j = ej[i][o];

		delete_(j, i);
		h_ = h;
		while (h_ < m && oo[ii[hh[h_]]] == o)
			h_++;
		cd(hh + h, h_ - h, sz[j] < sz[i] ? sz[j] : n - sz[i], j);
	}
}

int main() {
	static int hh[M];
	int h, i, i_, j, j_, x, y, lower, upper;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d%d", &xx[i], &yy[i]);
	for (i = 0; i < n; i++)
		ii[i] = i;
	sort(ii, 0, n);
	for (i = 0; i < n; i++)
		xx_[i] = xx[ii[i]], yy_[i] = yy[ii[i]];
	memcpy(xx, xx_, n * sizeof *xx_), memcpy(yy, yy_, n * sizeof *yy_);
	n_ = 0;
	for (i = 0; i < n; i = j) {
		j = i + 1;
		while (j < n && xx[j] == xx[j - 1] && yy[j] == yy[j - 1] + 1)
			j++;
		for (h = i; h < j; h++)
			ii[h] = n_;
		ll[n_] = i, rr[n_] = j - 1, n_++;
	}
	for (i = 0; i < n_; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (i = 0, j = 0; i < n; i++) {
		x = xx[i], y = yy[i];
		while (j < n && (xx[j] < x + 1 || xx[j] == x + 1 && yy[j] < y))
			j++;
		if (j < n && xx[j] == x + 1 && yy[j] == y) {
			i_ = ii[i], j_ = ii[j];
			if (ll[i_] == i || ll[j_] == j)
				append(i_, j_), append(j_, i_);
		}
	}
	scanf("%d", &m);
	for (h = 0; h < m; h++) {
		scanf("%d%d%d", &tt[h], &x, &y);
		lower = -1, upper = n;
		while (upper - lower > 1) {
			i = (lower + upper) / 2;
			if (xx[i] < x || xx[i] == x && yy[i] <= y)
				lower = i;
			else
				upper = i;
		}
		ii[h] = lower;
	}
	memset(ans, 0x3f, m * sizeof *ans);
	for (h = 0; h < m; h++)
		hh[h] = h;
	cd(hh, m, n_, 0);
	for (h = 0; h < m; h++)
		if (tt[h] == 2)
			printf("%d\n", ans[h] == INF ? -1 : ans[h]);
	return 0;
}

Compilation message (stderr)

C.c: In function 'append':
C.c:48:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   48 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
C.c: In function 'main':
C.c:204:52: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  204 |   while (j < n && (xx[j] < x + 1 || xx[j] == x + 1 && yy[j] < y))
      |                                     ~~~~~~~~~~~~~~~^~~~~~~~~~~~
C.c:218:32: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  218 |    if (xx[i] < x || xx[i] == x && yy[i] <= y)
      |                     ~~~~~~~~~~~^~~~~~~~~~~~~
C.c:182:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  182 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
C.c:184:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  184 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
C.c:212:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  212 |  scanf("%d", &m);
      |  ^~~~~~~~~~~~~~~
C.c:214:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  214 |   scanf("%d%d%d", &tt[h], &x, &y);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 19 / 19
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 29 / 29