oj.uz

Submission #925844

# Submission time Handle Problem Language Result Execution time Memory
925844 2024-02-12T09:56:15 Z mickey080929 Abduction 2 (JOI17_abduction2) C++17
13 / 100
 5000 ms 8792 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll H, W, Q;
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) {
	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);
	}
	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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8536 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 2 ms 8540 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8536 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 2 ms 8540 KB Output is correct
12 Correct 2 ms 8540 KB Output is correct
13 Correct 1 ms 8540 KB Output is correct
14 Correct 2 ms 8540 KB Output is correct
15 Correct 2 ms 8792 KB Output is correct
16 Correct 2 ms 8540 KB Output is correct
17 Correct 2 ms 8540 KB Output is correct
18 Correct 1 ms 8540 KB Output is correct
19 Execution timed out 5043 ms 8540 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8536 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 2 ms 8540 KB Output is correct
12 Correct 2 ms 8540 KB Output is correct
13 Correct 1 ms 8540 KB Output is correct
14 Correct 2 ms 8540 KB Output is correct
15 Correct 2 ms 8792 KB Output is correct
16 Correct 2 ms 8540 KB Output is correct
17 Correct 2 ms 8540 KB Output is correct
18 Correct 1 ms 8540 KB Output is correct
19 Execution timed out 5043 ms 8540 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8540 KB Output is correct
2 Correct 7 ms 8540 KB Output is correct
3 Correct 9 ms 8692 KB Output is correct
4 Correct 10 ms 8540 KB Output is correct
5 Correct 11 ms 8540 KB Output is correct
6 Correct 13 ms 8540 KB Output is correct
7 Correct 12 ms 8788 KB Output is correct
8 Execution timed out 5038 ms 8540 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8536 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 2 ms 8540 KB Output is correct
12 Correct 2 ms 8540 KB Output is correct
13 Correct 1 ms 8540 KB Output is correct
14 Correct 2 ms 8540 KB Output is correct
15 Correct 2 ms 8792 KB Output is correct
16 Correct 2 ms 8540 KB Output is correct
17 Correct 2 ms 8540 KB Output is correct
18 Correct 1 ms 8540 KB Output is correct
19 Execution timed out 5043 ms 8540 KB Time limit exceeded
20 Halted 0 ms 0 KB -