Submission #63609

#	Time	Username	Problem	Language	Result	Execution time	Memory
63609		zadrga	Abduction 2 (JOI17_abduction2)	C++14	0 / 100	1655 ms	525312 KiB

abduction2

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF ((int) 1e9)
#define MOD (1000 * 1000 * 1000 + 7)
#define maxn 50111
#define logn 17

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

int segd[maxn][logn], segu[maxn][logn], segl[maxn][logn], segr[maxn][logn];
int a[maxn], b[maxn];
int h, w, q;

map<ll, int> dp;

int findPos(int x, int val, int n, int sign, int arr[maxn][logn]){
	int cur = x;
	for(int i = logn - 1; i >= 0; i--){
		int pos = cur + sign * ((1 << i) - 1);
		if(cur < 0 || cur >= n)
			break;

		if(arr[cur][i] < val)
			cur = pos;
	}

	if(cur >= n)
		return n;

	if(cur < 0)
		return -1;
	
	if(arr[cur][0] < val)
		cur += sign;

	return cur;
}


int f(int x, int y, int dir){
	ll id = x * 2 * maxn + 2 * y + dir;
	if(dp.count(id))
		return dp[id];

//	cout << x << "  " << y << "  " << dir << endl;

	int cur = 0;
	if(dir == 0){	// left
		int pos = findPos(y - 1, a[x], w, -1, segl);
		int dist = abs(pos - y);

		if(pos < 0){
			cur = max(cur, dist - 1);
		}
		else{
			cur = max(cur, f(x, pos, 1) + dist);
			cur = max(cur, f(x, pos, 1) + dist);
		}
	}

	if(dir == 0){	// right
		int pos = findPos(y + 1, a[x], w, 1, segr);
		int dist = abs(pos - y);

		if(pos == w){
			cur = max(cur, dist - 1);
		}
		else{
			cur = max(cur, f(x, pos, 1) + dist);
			cur = max(cur, f(x, pos, 1) + dist);
		}
	}

	if(dir == 1){	// down
		int pos = findPos(x + 1, b[y], h, 1, segd);
		int dist = abs(pos - x);

		if(pos == h){
			cur = max(cur, dist - 1);
		}
		else{	
			cur = max(cur, f(pos, y, 0) + dist);
			cur = max(cur, f(pos, y, 0) + dist);
		}
	}

	if(dir == 1){	// up
		int pos = findPos(x - 1, b[y], h, -1, segu);
		int dist = abs(pos - x);

		if(pos < 0){
			cur = max(cur, dist - 1);
		}
		else{
			cur = max(cur, f(pos, y, 0) + dist);
			cur = max(cur, f(pos, y, 0) + dist);
		}
	}
	dp[id] = cur;
	return cur;
}

void precalc(){
	for(int i = 0; i < h; i++)
		segu[i][0] = segd[i][0] = a[i];

	for(int j = 1; j < logn; j++){
		for(int i = 0; i < h; i++){
			segd[i][j] = segd[i][j - 1];
			int pos = i + (1 << (j - 1));
			if(pos < h)
				segd[i][j] = max(segd[i][j], segd[pos][j - 1]);

			segu[i][j] = segu[i][j - 1];
			pos = i - (1 << (j - 1));
			if(pos >= 0)
				segu[i][j] = max(segu[i][j], segu[pos][j - 1]);
		}
	}

	for(int i = 0; i < w; i++)
		segl[i][0] = segr[i][0] = b[i];

	for(int j = 1; j < logn; j++){
		for(int i = 0; i < w; i++){
			segr[i][j] = segr[i][j - 1];
			int pos = i + (1 << (j - 1));
			if(pos < w)
				segr[i][j] = max(segr[i][j], segr[pos][j - 1]);

			segl[i][j] = segl[i][j - 1];
			pos = i - (1 << (j - 1));
			if(pos >= 0)
				segl[i][j] = max(segl[i][j], segl[pos][j - 1]);
		}
	}
}

int main(){
	scanf("%d%d%d", &h, &w, &q);
	for(int i = 0; i < h; i++)
		scanf("%d", a + i);

	for(int i = 0; i < w; i++)
		scanf("%d", b + i);

	precalc();

	while(q--){
		int x, y, ans = 0;
		scanf("%d%d", &x, &y);
		x--; y--;
		for(int i = 0; i < 2; i++)
			ans = max(ans, f(x, y, i));

		printf("%d\n", ans);
	}
	return 0;
}

Compilation message (stderr)

abduction2.cpp: In function 'int main()':
abduction2.cpp:148:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &h, &w, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
abduction2.cpp:150:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", a + i);
   ~~~~~^~~~~~~~~~~~~
abduction2.cpp:153:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", b + i);
   ~~~~~^~~~~~~~~~~~~
abduction2.cpp:159:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~

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