Submission #925842

#	Time	Username	Problem	Language	Result	Execution time	Memory
925842		mickey080929	Abduction 2 (JOI17_abduction2)	C++17	100 / 100	854 ms	152176 KiB

abduction2

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll H, W, Q;
map<ll,ll> memo;
ll mxl[50010][16], mxr[50010][16], mxu[50010][16], mxd[50010][16];
ll A[50010], B[50010];

ll dfs(ll x, ll y, ll dir) {
	if (memo.find(x*W*2 + y*2 + dir) != memo.end()) return memo[x*W*2 + y*2 + dir];
	ll cur = 0;
	if (dir == 0) {
		ll u = x - 1, d = x + 1;
		for (ll lv=15; lv>=0; lv--) {
			if (u - (1 << lv) >= -1 && mxu[u][lv] < B[y])
				u -= (1 << lv);
			if (d + (1 << lv) <= H && mxd[d][lv] < B[y])
				d += (1 << lv);
		}
		if (u != -1) cur = max(cur, dfs(u, y, 1) + x - u);
		else cur = max(cur, x);
		if (d != H) cur = max(cur, dfs(d, y, 1) + d - x);
		else cur = max(cur, H - x - 1);
	}
	else {
		ll l = y - 1, r = y + 1; 
		for (ll lv=15; lv>=0; lv--) {
			if (l - (1 << lv) >= -1 && mxl[l][lv] < A[x])
				l -= (1 << lv);
			if (r + (1 << lv) <= W && mxr[r][lv] < A[x])
				r += (1 << lv);
		}
		if (l != -1) cur = max(cur, dfs(x, l, 0) + y - l);
		else cur = max(cur, y);
		if (r != W) cur = max(cur, dfs(x, r, 0) + r - y);
		else cur = max(cur, W - y - 1);
	}
	memo[x*W*2 + y*2 + dir] = cur;
	return cur;
}

int main() {
	ios_base :: sync_with_stdio(false); cin.tie(NULL); 
	cin >> H >> W >> Q;
	for (ll i=0; i<H; i++) {
		cin >> A[i];
		mxu[i][0] = mxd[i][0] = A[i];
	}
	for (ll i=0; i<W; i++) {
		cin >> B[i];
		mxl[i][0] = mxr[i][0] = B[i];
	}
	for (ll lv=1; lv<=15; lv++) {
		for (ll i=0; i<H; i++) {
			if (i - (1 << lv) >= -1)
				mxu[i][lv] = max(mxu[i][lv-1], mxu[i-(1<<(lv-1))][lv-1]);
			if (i + (1 << lv) <= H)
				mxd[i][lv] = max(mxd[i][lv-1], mxd[i+(1<<(lv-1))][lv-1]);
		}
	}
	for (ll lv=1; lv<=15; lv++) {
		for (ll i=0; i<W; i++) {
			if (i - (1 << lv) >= -1)
				mxl[i][lv] = max(mxl[i][lv-1], mxl[i-(1<<(lv-1))][lv-1]);
			if (i + (1 << lv) <= W)
				mxr[i][lv] = max(mxr[i][lv-1], mxr[i+(1<<(lv-1))][lv-1]);
		}
	}
	while (Q --) {
		ll x, y;
		cin >> x >> y;
		x --; y --;
		cout << max(dfs(x, y, 0), dfs(x, y, 1)) << '\n';
	}
}

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