oj.uz

Submission #719425

# Submission time Handle Problem Language Result Execution time Memory
719425 2023-04-05T22:10:54 Z rainboy Circus (Balkan15_CIRCUS) C++17
100 / 100
 1129 ms 23536 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 5696 KB Output is correct
2 Correct 175 ms 6032 KB Output is correct
3 Correct 184 ms 5824 KB Output is correct
4 Correct 193 ms 5724 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 432 KB Output is correct
6 Correct 3 ms 432 KB Output is correct
7 Correct 3 ms 432 KB Output is correct
8 Correct 3 ms 436 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 432 KB Output is correct
6 Correct 3 ms 432 KB Output is correct
7 Correct 3 ms 432 KB Output is correct
8 Correct 3 ms 436 KB Output is correct
9 Correct 397 ms 17740 KB Output is correct
10 Correct 344 ms 10608 KB Output is correct
11 Correct 385 ms 9932 KB Output is correct
12 Correct 405 ms 18720 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 5696 KB Output is correct
2 Correct 175 ms 6032 KB Output is correct
3 Correct 184 ms 5824 KB Output is correct
4 Correct 193 ms 5724 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 292 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 3 ms 432 KB Output is correct
10 Correct 3 ms 432 KB Output is correct
11 Correct 3 ms 432 KB Output is correct
12 Correct 3 ms 436 KB Output is correct
13 Correct 207 ms 6012 KB Output is correct
14 Correct 186 ms 5956 KB Output is correct
15 Correct 174 ms 5548 KB Output is correct
16 Correct 176 ms 5552 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 5696 KB Output is correct
2 Correct 175 ms 6032 KB Output is correct
3 Correct 184 ms 5824 KB Output is correct
4 Correct 193 ms 5724 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 292 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 3 ms 432 KB Output is correct
10 Correct 3 ms 432 KB Output is correct
11 Correct 3 ms 432 KB Output is correct
12 Correct 3 ms 436 KB Output is correct
13 Correct 397 ms 17740 KB Output is correct
14 Correct 344 ms 10608 KB Output is correct
15 Correct 385 ms 9932 KB Output is correct
16 Correct 405 ms 18720 KB Output is correct
17 Correct 207 ms 6012 KB Output is correct
18 Correct 186 ms 5956 KB Output is correct
19 Correct 174 ms 5548 KB Output is correct
20 Correct 176 ms 5552 KB Output is correct
21 Correct 1122 ms 17760 KB Output is correct
22 Correct 1129 ms 17984 KB Output is correct
23 Correct 1048 ms 21108 KB Output is correct
24 Correct 1087 ms 23536 KB Output is correct