Submission #719425

#	Time	Username	Problem	Language	Result	Execution time	Memory
719425		rainboy	Circus (Balkan15_CIRCUS)	C++17	100 / 100	1129 ms	23536 KiB

circus

#include "circus.h"
#include <string.h>

const int N = 100001;
const int INF = 0x3f3f3f3f;

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 xx[N], xx1[N], xx2[N], yy[N], ii[N], ii1[N], ii2[N], n;

int compare_x(int i, int j) {
	return xx[i] - xx[j];
}

int compare_xpy(int i, int j) {
	return (xx[i] + yy[i]) - (xx[j] + yy[j]);
}

int compare_xmy(int i, int j) {
	return (xx[i] - yy[i]) - (xx[j] - yy[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 dd[N * 2], iq[N * 2 + 1], pq[N * 2], cnt;

int lt(int i, int j) { return dd[i] < dd[j]; }

int p2(int p) {
	return (p *= 2) > cnt ? 0 : (p < cnt && lt(iq[p + 1], iq[p]) ? p + 1 : p);
}

void pq_up(int i) {
	int p, q, j;
	for (p = pq[i]; (q = p / 2) && lt(i, j = iq[q]); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_dn(int i) {
	int p, q, j;
	for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_add_last(int i) {
	iq[pq[i] = ++cnt] = i;
}

int pq_remove_first() {
	int i = iq[1], j = iq[cnt--];
	if (j != i)
		pq[j] = 1, pq_dn(j);
	pq[i] = 0;
	return i;
}

void init(int n_, int m, int *xx_) {
	n = n_;
	for (int i = 0; i < n; i++)
		xx[i] = xx_[i];
	xx[n++] = m;
	for (int i = 0; i < n; i++)
		ii[i] = i;
	compare = compare_x, sort(ii, 0, n);
	memset(dd, 0x3f, n * 2 * sizeof *dd);
	dd[n - 1 << 1 | 0] = 0, pq_add_last(n - 1 << 1 | 0);
	while (cnt) {
		int u, v, i, t, d;
		u = pq_remove_first(), i = u >> 1, t = (u & 1);
		if (t == 0) {
			if (i > 0) {
				v = i - 1 << 1 | 0, d = dd[u] + xx[ii[i]] - xx[ii[i - 1]];
				if (dd[v] > d) {
					if (dd[v] == INF)
						pq_add_last(v);
					dd[v] = d, pq_up(v);
				}
			}
		} else {
			if (i + 1 < n) {
				v = i + 1 << 1 | 1, d = dd[u] + xx[ii[i + 1]] - xx[ii[i]];
				if (dd[v] > d) {
					if (dd[v] == INF)
						pq_add_last(v);
					dd[v] = d, pq_up(v);
				}
			}
		}
		int lower, upper, j;
		lower = i - 1, upper = n;
		while (upper - lower > 1) {
			j = (lower + upper) / 2;
			if (xx[ii[j]] - xx[ii[i]] >= dd[u])
				upper = j;
			else
				lower = j;
		}
		j = upper;
		if (j < n) {
			v = j << 1 | 1, d = xx[ii[j]] - xx[ii[i]];
			if (dd[v] > d) {
				if (dd[v] == INF)
					pq_add_last(v);
				dd[v] = d, pq_up(v);
			}
		}
		lower = -1, upper = i + 1;
		while (upper - lower > 1) {
			j = (lower + upper) / 2;
			if (xx[ii[i]] - xx[ii[j]] >= dd[u])
				lower = j;
			else
				upper = j;
		}
		j = lower;
		if (j >= 0) {
			v = j << 1 | 0, d = xx[ii[i]] - xx[ii[j]];
			if (dd[v] > d) {
				if (dd[v] == INF)
					pq_add_last(v);
				dd[v] = d, pq_up(v);
			}
		}
	}
	for (int i = 0; i < n; i++)
		yy[ii[i]] = min(dd[i << 1 | 0], dd[i << 1 | 1]);
	for (int i = 0; i < n; i++)
		ii1[i] = i;
	compare = compare_xpy, sort(ii1, 0, n);
	for (int i = 0; i < n; i++)
		xx1[i] = max(i == 0 ? -INF : xx1[i - 1], xx[ii1[i]]);
	for (int i = 0; i < n; i++)
		ii2[i] = i;
	compare = compare_xmy, sort(ii2, 0, n);
	for (int i = n - 1; i >= 0; i--)
		xx2[i] = min(i + 1 == n ? INF : xx2[i + 1], xx[ii2[i]]);
}

int minLength(int x) {
	int lower, upper, i, ans;
	ans = INF;
	lower = -1, upper = n;
	while (upper - lower > 1) {
		i = (lower + upper) / 2;
		if (xx[ii1[i]] + yy[ii1[i]] <= x)
			lower = i;
		else
			upper = i;
	}
	i = lower;
	if (i >= 0)
		ans = min(ans, x - xx1[i]);
	lower = -1, upper = n;
	while (upper - lower > 1) {
		i = (lower + upper) / 2;
		if (xx[ii2[i]] - yy[ii2[i]] >= x)
			upper = i;
		else
			lower = i;
	}
	i = upper;
	if (i < n)
		ans = min(ans, xx2[i] - x);
	return ans;
}

Compilation message (stderr)

circus.cpp: In function 'void init(int, int, int*)':
circus.cpp:95:7: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   95 |  dd[n - 1 << 1 | 0] = 0, pq_add_last(n - 1 << 1 | 0);
      |     ~~^~~
circus.cpp:95:40: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   95 |  dd[n - 1 << 1 | 0] = 0, pq_add_last(n - 1 << 1 | 0);
      |                                      ~~^~~
circus.cpp:101:11: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  101 |     v = i - 1 << 1 | 0, d = dd[u] + xx[ii[i]] - xx[ii[i - 1]];
      |         ~~^~~
circus.cpp:110:11: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  110 |     v = i + 1 << 1 | 1, d = dd[u] + xx[ii[i + 1]] - xx[ii[i]];
      |         ~~^~~
grader.cpp: In function 'int main()':
grader.cpp:14:12: warning: unused variable 'max_code' [-Wunused-variable]
   14 |  long long max_code;
      |            ^~~~~~~~
grader.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |  scanf("%d%d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~
grader.cpp:18:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |   scanf("%d", &P[i]);
      |   ~~~~~^~~~~~~~~~~~~
grader.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
grader.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |   scanf("%d", &d);
      |   ~~~~~^~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 17 / 17
• Subtask 3: 23 / 23
• Subtask 4: 9 / 9
• Subtask 5: 31 / 31
• Subtask 6: 9 / 9