oj.uz

Submission #282189

# Submission time Handle Problem Language Result Execution time Memory
282189 2020-08-24T06:13:23 Z 임성재(#5755) Abduction 2 (JOI17_abduction2) C++17
0 / 100
 826 ms 60024 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf = 1e9 + 7;
const ll INF = 1e18;

int n, m, q;
int a[50010];
int b[50010];
vector<pii> v;
int ans[2][2010][2010];
bool chk[100010];

int main() {
	fast;

	cin >> n >> m >> q;

	for(int i=1; i<=n; i++) {
		cin >> a[i];

		v.eb(a[i], i);
	}

	for(int i=1; i<=m; i++) {
		cin >> b[i];

		v.eb(b[i], i+n);
	}

	sort(all(v));
	reverse(all(v));

	for(int i=1; i<=n; i++) {
		for(int j=1; b[j] < a[i] && j <= m; j++) {
			ans[0][i][j] = max(ans[0][i][j], j-1);
		}

		for(int j = m; b[j] < a[i] && j>=1; j--) {
			ans[0][i][j] = max(ans[0][i][j], m - j);
		}
	}

	for(int i=1; i<=m; i++) {
		for(int j=1; a[j] < b[i] && j<=n; j++) {
			ans[1][j][i] = max(ans[1][j][i], j-1);
		}

		for(int j = n; a[j] < b[i] && j>=1; j--) {
			ans[1][j][i] = max(ans[1][j][i], n - j);
		}
	}

	for(auto x : v) {
		chk[x.se] = true;

		if(x.se <= n) {
			for(int i=1; i<=m; i++) {
				if(a[x.se] < b[i]) continue;
				for(int j = x.se + 1; a[j] < b[i] && j<=n; j++) {
					ans[1][j][i] = max(ans[1][j][i], ans[0][x.se][i] + j - x.se);
				}

				for(int j = x.se - 1; a[j] < b[i] && j>=1; j--) {
					ans[1][j][i] = max(ans[1][j][i], ans[0][x.se][i] + x.se - j);
				}
			}
		}
		else{
			for(int i=1; i<=n; i++) {
				if(b[x.se-n] < a[i]) continue;
				for(int j = x.se - n + 1; b[j] < a[i] && j<=m; j++) {
					ans[0][i][j] = max(ans[0][i][j], ans[1][i][x.se-n] + j - x.se + n);
				}

				for(int j = x.se - n - 1; b[j] < a[i] && j>=0; j--) {
					ans[0][i][j] = max(ans[0][i][j], ans[1][i][x.se-n] + x.se - n - j);
				}
			}
		}
	}

	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			cout << ans[0][i][j] << " ";
		}
		cout << "\n";
	}
	cout << "\n";

	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			cout << ans[1][i][j] << " ";
		}
		cout << "\n";
	}

	while(q--) {
		int x, y;
		cin >> x >> y;

		int ret = 0;

		for(int i=x+1; i<=n; i++) {
			ret = max(ret, abs(i - x) + ans[0][i][y]);
			if(b[y] < a[i]) break;
		}

		for(int i=x-1; i>=1; i--) {
			ret = max(ret, abs(i - x) + ans[0][i][y]);
			if(b[y] < a[i]) break;
		}

		for(int i=y+1; i<=m; i++) {
			ret = max(ret, abs(i - y) + ans[1][x][i]);
			if(a[x] < b[i]) break;
		}

		for(int i=y-1; i>=1; i--) {
			ret = max(ret, abs(i - y) + ans[1][x][i]);
			if(a[x] < b[i]) break;
		}

		cout << ret << "\n";
	}
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 826 ms 60024 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 56.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -