Submission #163413

#	Time	Username	Problem	Language	Result	Execution time	Memory
163413		iefnah06	Abduction 2 (JOI17_abduction2)	C++11	100 / 100	1832 ms	137460 KiB

abduction2

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int INF = 1.1e9;

const int MAXN = 5.1e4;
const int MAXQ = 110;
int H, W;
int Q;

struct RMQ {
	int N;
	int A[MAXN];
	int table[16][MAXN];

	void init() {
		A[0] = A[N+1] = INF;
		N += 2;
		for (int i = 0; i < N; i++) {
			table[0][i] = A[i];
		}
		for (int i = 1; (1 << i) <= N; i++) {
			for (int j = 0; j + (1 << i) <= N; j++) {
				table[i][j] = max(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
			}
		}
	}

	int query(int l, int r) { // exclusive
		assert(l < r);
		int k = 31 - __builtin_clz(r-l);
		return max(table[k][l], table[k][r - (1 << k)]);
	}

	int find_prev(int i, int v) {
		int mi = 0;
		int ma = i;
		while (ma - mi > 1) {
			int md = (mi + ma) / 2;
			if (query(md, i) > v) {
				mi = md;
			} else {
				ma = md;
			}
		}
		assert(mi < i);
		return mi;
	}

	int find_next(int i, int v) {
		int mi = i;
		int ma = N-1;
		while (ma - mi > 1) {
			int md = (mi + ma) / 2;
			if (query(i+1, md+1) > v) {
				ma = md;
			} else {
				mi = md;
			}
		}
		assert(ma > i);
		return ma;
	}
} rmqs[2];

map<int, ll> dp[2][MAXN];
ll go(int dir, int r, int c) {
	if (dp[dir][r].count(c)) {
		return dp[dir][r][c];
	}

	ll ans = 0;
	if (dir == 0) {
		int r0 = rmqs[0].find_prev(r, rmqs[1].A[c]);
		int r1 = rmqs[0].find_next(r, rmqs[1].A[c]);
		ans = max(ans, r0 >= 1 ? go(1, r0, c) + r - r0 : r-1);
		ans = max(ans, r1 <= H ? go(1, r1, c) + r1 - r : H-r);
	} else {
		int c0 = rmqs[1].find_prev(c, rmqs[0].A[r]);
		int c1 = rmqs[1].find_next(c, rmqs[0].A[r]);
		ans = max(ans, c0 >= 1 ? go(0, r, c0) + c - c0 : c-1);
		ans = max(ans, c1 <= W ? go(0, r, c1) + c1 - c : W-c);
	}
	return dp[dir][r][c] = ans;
}

int main() {
	cin >> H >> W >> Q;
	for (int i = 1; i <= H; i++) {
		cin >> rmqs[0].A[i];
	}
	for (int i = 1; i <= W; i++) {
		cin >> rmqs[1].A[i];
	}
	rmqs[0].N = H;
	rmqs[1].N = W;
	rmqs[0].init();
	rmqs[1].init();

	while (Q--) {
		int s, t; cin >> s >> t;
		ll ans = max(go(0, s, t), go(1, s, t));
		cout << ans << '\n';
	}

	return 0;
}

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