Submission #205264

#	Time	Username	Problem	Language	Result	Execution time	Memory
205264		hanagasumi	Abduction 2 (JOI17_abduction2)	C++17	100 / 100	3385 ms	153784 KiB

abduction2

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <deque>
#include <map>
#include <set>
#include <complex>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <chrono>
 
#define ft first
#define sc second
#define pb push_back
#define len(v) (int)v.size()
#define int ll

using namespace std;
typedef long long ll;
typedef long double ld;

vector<int> logt;

void built_logt(int n) {
	logt = vector<int> (n + 2, 0);
	int cnt = 0, now = 1;
	for (int i = 0; i <= n + 1; i++) {
		if(now * 2 == i) {
			now *= 2;
			cnt++;
		}
		logt[i] = cnt;
	}
	return;
}

struct sparse {
	vector<vector<int>> table;
	int n, log;
	sparse() {}
	sparse(vector<int>& have) {
		n = len(have);
		log = 1;
		while((1 << log) <= n) 
			log *= 2;
		table = vector<vector<int>> (log + 1, vector<int> (n + 1, 0));
		for (int i = 0; i < n; i++) {
			table[0][i] = have[i];
		}
		for (int logn = 1; logn < log; logn++) {
			for (int i = 0; i < n; i++) {
				int nxt = min(n - 1, (1 << (logn - 1)) + i);
				table[logn][i] = max(table[logn - 1][i], table[logn - 1][nxt]);
			}
		}
		return;
	}
	int get(int l, int r) {
		// int ans = 0;
		// for (int i = l; i <= r; i++) {
		// 	ans = max(table[0][i], ans);
		// }
		// return ans;
		int lenn = (r - l + 1);
		int logn = logt[lenn];
		int pred = (r - (1 << logn) + 1);
		int ans = max(table[logn][l], table[logn][pred]);
		return ans;
	}
};

map<pair<int, int>, int> dp;
int w, h;
vector<int> a;
vector<int> b;
sparse as;
sparse bs;

int solve(int i, int j) {
	// cout << i << " " << j << endl;
	// cout << a[i] << " " << b[j] << endl;
	if(dp.count({i, j})) 
		return dp[{i, j}];
	if(a[i] > b[j]) {

		int l = j, r = w;
		while(r - l > 1) {
			int now = (l + r) / 2;
			if(bs.get(j, now) > a[i]) 
				r = now;
			else
				l = now;
		}

		if(r == w) 
			dp[{i, j}] = max(dp[{i, j}], w - j);
		else
			dp[{i, j}] = max(dp[{i, j}], r - j + solve(i, r));

		l = -1, r = j;
		while(r - l > 1) {
			int now = (l + r) / 2;
			if(bs.get(now, j) > a[i]) 
				l = now;
			else
				r = now;
		}
		if(l == -1) 
			dp[{i, j}] = max(dp[{i, j}], j + 1);
		else
			dp[{i, j}] = max(dp[{i, j}], j - l + solve(i, l));
	}
	else {


		int l = i, r = h;
		while(r - l > 1) {
			int now = (l + r) / 2;
			if(as.get(i, now) > b[j]) 
				r = now;
			else
				l = now;
		}
		if(r == h) 
			dp[{i, j}] = max(dp[{i, j}], h - i);
		else
			dp[{i, j}] = max(dp[{i, j}], r - i + solve(r, j));

		l = -1, r = i;
		while(r - l > 1) {
			int now = (l + r) / 2;
			if(as.get(now, i) > b[j]) 
				l = now;
			else
				r = now;
		}
		if(l == -1) 
			dp[{i, j}] = max(dp[{i, j}], i + 1);
		else
			dp[{i, j}] = max(dp[{i, j}], i - l + solve(l, j));
	}
	return dp[{i, j}];
}


signed main() {
	#ifdef PC 
		freopen("in.txt", "r", stdin);
		freopen("out.txt", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int q;
	cin >> h >> w >> q;
	a = vector<int> (h);
	b = vector<int> (w);
	for (int i = 0; i < h; i++) {
		cin >> a[i];
	}
	for (int j = 0; j < w; j++) {
		cin >> b[j];
	}
	built_logt(w + h);
	as = *new sparse(a);
	bs = *new sparse(b);
	for (int k = 0; k < q; k++) {
		int i, j;
		cin >> i >> j;
		i--, j--;
		int ans = 1;
		for (int j1 = j + 1; j1 < w; j1++) {
			ans = max(ans, j1 - j + 1);
			if(b[j1] > a[i]) {
				ans = max(ans, j1 - j + solve(i, j1));
				break;
			}
		}
		for (int j1 = j - 1; j1 >= 0; j1--) {
			ans = max(ans, j - j1 + 1);
			if(b[j1] > a[i]) {
				ans = max(ans, j - j1 + solve(i, j1));
				break;
			}
		}
		for (int i1 = i + 1; i1 < h; i1++) {
			ans = max(ans, i1 - i + 1);
			if(a[i1] > b[j]) {
				ans = max(ans, i1 - i + solve(i1, j));
				break;
			}
		}
		for (int i1 = i - 1; i1 >= 0; i1--) {
			ans = max(ans, i - i1 + 1);
			if(a[i1] > b[j]) {
				ans = max(ans, i - i1 + solve(i1, j));
				break;
			}
		}

		cout << ans - 1 << '\n';
	}

}

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