Submission #684216

#	Time	Username	Problem	Language	Result	Execution time	Memory
684216		rainboy	Abduction 2 (JOI17_abduction2)	C11	44 / 100	5022 ms	5304 KiB

abduction2

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

#define N	50000
#define M	50000
#define K	(N + M)

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

unsigned int X = 12345;

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

int aa[N], bb[M], cc[K], hh[K], n, m, k;

void sort(int *hh, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (cc[hh[j]] == cc[h])
				j++;
			else if (cc[hh[j]] < cc[h]) {
				tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
			}
		sort(hh, l, i);
		l = k;
	}
}

long long solve(int i_, int j_) {
	static int iil[N], iir[N], jjl[M], jjr[M], iil_[M], iir_[M], jjl_[N], jjr_[N];
	static long long dpl[K], dpr[K];
	int nl, nr, ml, mr, h, h_, i, j, lower, upper;
	long long x, ans;

	nl = 0;
	for (i = i_; i >= 0; i--)
		if (nl == 0 || aa[iil[nl - 1]] < aa[i])
			iil[nl++] = i;
	nr = 0;
	for (i = i_; i < n; i++)
		if (nr == 0 || aa[iir[nr - 1]] < aa[i])
			iir[nr++] = i;
	ml = 0;
	for (j = j_; j >= 0; j--)
		if (ml == 0 || bb[jjl[ml - 1]] < bb[j])
			jjl[ml++] = j;
	mr = 0;
	for (j = j_; j < m; j++)
		if (mr == 0 || bb[jjr[mr - 1]] < bb[j])
			jjr[mr++] = j;
	for (i = 0; i < n; i++) {
		lower = -1, upper = ml;
		while (upper - lower > 1) {
			j = (lower + upper) / 2;
			if (bb[jjl[j]] > aa[i])
				upper = j;
			else
				lower = j;
		}
		jjl_[i] = upper == ml ? -1 : jjl[upper];
		lower = -1, upper = mr;
		while (upper - lower > 1) {
			j = (lower + upper) / 2;
			if (bb[jjr[j]] > aa[i])
				upper = j;
			else
				lower = j;
		}
		jjr_[i] = upper == mr ? -1 : jjr[upper];
	}
	for (j = 0; j < m; j++) {
		lower = -1, upper = nl;
		while (upper - lower > 1) {
			i = (lower + upper) / 2;
			if (aa[iil[i]] > bb[j])
				upper = i;
			else
				lower = i;
		}
		iil_[j] = upper == nl ? -1 : iil[upper];
		lower = -1, upper = nr;
		while (upper - lower > 1) {
			i = (lower + upper) / 2;
			if (aa[iir[i]] > bb[j])
				upper = i;
			else
				lower = i;
		}
		iir_[j] = upper == nr ? -1 : iir[upper];
	}
	memset(dpl, -1, k * sizeof *dpl), memset(dpr, -1, k * sizeof *dpr);
	if (aa[i_] > bb[j_])
		dpl[n + j_] = 0;
	else
		dpl[i_] = 0;
	ans = 0;
	for (h = 0; h < k; h++) {
		h_ = hh[h];
		if (h_ < n)
			i = h_;
		else
			j = h_ - n;
		if (h_ < n) {
			if ((x = dpl[h_]) != -1) {
				j = jjl_[i];
				if ((i_ = iil_[j]) == -1)
					ans = max(ans, x + i);
				else
					dpl[n + j] = max(dpl[n + j], x + i - i_);
				if ((i_ = iir_[j]) == -1)
					ans = max(ans, x + n - 1 - i);
				else
					dpr[n + j] = max(dpr[n + j], x + i_ - i);
			}
			if ((x = dpr[h_]) != -1) {
				j = jjr_[i];
				if ((i_ = iil_[j]) == -1)
					ans = max(ans, x + i);
				else
					dpl[n + j] = max(dpl[n + j], x + i - i_);
				if ((i_ = iir_[j]) == -1)
					ans = max(ans, x + n - 1 - i);
				else
					dpr[n + j] = max(dpr[n + j], x + i_ - i);
			}
		} else {
			if ((x = dpl[h_]) != -1) {
				i = iil_[j];
				if ((j_ = jjl_[i]) == -1)
					ans = max(ans, x + j);
				else
					dpl[i] = max(dpl[i], x + j - j_);
				if ((j_ = jjr_[i]) == -1)
					ans = max(ans, x + m - 1 - j);
				else
					dpr[i] = max(dpr[i], x + j_ - j);
			}
			if ((x = dpr[h_]) != -1) {
				i = iir_[j];
				if ((j_ = jjl_[i]) == -1)
					ans = max(ans, x + j);
				else
					dpl[i] = max(dpl[i], x + j - j_);
				if ((j_ = jjr_[i]) == -1)
					ans = max(ans, x + m - 1 - j);
				else
					dpr[i] = max(dpr[i], x + j_ - j);
			}
		}
	}
	return ans;
}

int main() {
	int q, h, i, j;

	scanf("%d%d%d", &n, &m, &q), k = n + m;
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]);
	for (j = 0; j < m; j++)
		scanf("%d", &bb[j]);
	for (h = 0; h < k; h++)
		cc[h] = h < n ? aa[h] : bb[h - n];
	for (h = 0; h < k; h++)
		hh[h] = h;
	sort(hh, 0, k);
	while (q--) {
		int i, i_, j, j_;
		long long ans;

		scanf("%d%d", &i, &j), i--, j--;
		ans = -1;
		i_ = i - 1;
		while (i_ >= 0 && aa[i_] < bb[j])
			i_--;
		if (i_ < 0)
			ans = max(ans, i);
		else
			ans = max(ans, i - i_ + solve(i_, j));
		i_ = i + 1;
		while (i_ < n && aa[i_] < bb[j])
			i_++;
		if (i_ >= n)
			ans = max(ans, n - 1 - i);
		else
			ans = max(ans, i_ - i + solve(i_, j));
		j_ = j - 1;
		while (j_ >= 0 && bb[j_] < aa[i])
			j_--;
		if (j_ < 0)
			ans = max(ans, j);
		else
			ans = max(ans, j - j_ + solve(i, j_));
		j_ = j + 1;
		while (j_ < m && bb[j_] < aa[i])
			j_++;
		if (j_ >= m)
			ans = max(ans, m - 1 - j);
		else
			ans = max(ans, j_ - j + solve(i, j_));
		printf("%lld\n", ans);
	}
	return 0;
}

Compilation message (stderr)

abduction2.c: In function 'main':
abduction2.c:165:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |  scanf("%d%d%d", &n, &m, &q), k = n + m;
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
abduction2.c:167:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
abduction2.c:169:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |   scanf("%d", &bb[j]);
      |   ^~~~~~~~~~~~~~~~~~~
abduction2.c:179:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  179 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 10 / 10
• Subtask 3: 17 / 17
• Subtask 4: 4 / 4
• Subtask 5: 0 / 56