Submission #1214755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214755		NAMIN	Abduction 2 (JOI17_abduction2)	C++20	13 / 100	5092 ms	640 KiB

abduction2

#include <bits/stdc++.h>

#define ll long long
#define endl "\n"

using namespace std;

int N,M,Q;
vector<int> a,b;
vector<int> depi{0,0,-1,1};
vector<int> depj{1,-1,0,0};

bool ok(int curi,int curj){
	return (curi < N && curi >= 0 && curj < M && curj >= 0);
}

ll dfs(int curi,int curj,int di,int dj){
	if(di!=0){
		if(a[curi]<b[curj]){
			if(ok(curi+di,curj))
				return dfs(curi+di,curj,di,dj)+1;
			else
				return 0;
		}
		else{
			ll res = 0;
			if(ok(curi,curj+1))
				res = max(res,dfs(curi,curj+1,0,1)+1);
			if(ok(curi,curj-1))
				res = max(res,dfs(curi,curj-1,0,-1)+1);
			return res;
		}
	}
	else{
		if(a[curi]>b[curj]){
			if(ok(curi,curj+dj))
				return dfs(curi,curj+dj,di,dj)+1;
			else
				return 0;
		}
		else{
			ll res = 0;
			if(ok(curi+1,curj))
				res = max(res,dfs(curi+1,curj,1,0)+1);
			if(ok(curi-1,curj))
				res = max(res,dfs(curi-1,curj,-1,0)+1);
			return res;
		}
	}
}

void solve(){
	cin >> N >> M >> Q;
	a.resize(N),b.resize(M);
	for(int i=0;i<N;i++)
		cin >> a[i];
	for(int i=0;i<M;i++)
		cin >> b[i];

	while(Q--){
		int curi,curj;
		cin >> curi >> curj;
		curi--,curj--;
		ll ans = 0;
		for(int d=0;d<4;d++){
			if(curi+depi[d] >= N || curi+depi[d] < 0
					|| curj+depj[d] >= M || curj+depj[d] < 0)
				continue;
			ans = max(ans,dfs(curi+depi[d],curj+depj[d],depi[d],depj[d])+1);
		}
		cout << ans << endl;
	}
}	

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t = 1;
	//cin >> t;
 	while(t--){
		solve();
	}
	return 0;
}

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