Submission #624789

#	Time	Username	Problem	Language	Result	Execution time	Memory
624789		CSQ31	Abduction 2 (JOI17_abduction2)	C++17	44 / 100	65 ms	24528 KiB

abduction2

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
typedef pair<int,int> pii;
const int MAXN = 5e4+5;
vector<int>a,b;
int h,w,q;
map<int,int>dp[2][MAXN];
int lg[MAXN];
struct SPT
{
	vector<int>lg;
	vector<vector<int>> s;
	//zero indexed
	//modify s and a to whatever type works
	SPT(){}
	SPT(int n,int lim,vector<int>a)
	{
		s.resize(n);
		lg.resize(n+1);
		lg[1] = 0;
		for(int i=2;i<=n;i++)lg[i] = lg[i/2]+1;
		for(int i=0;i<n;i++){
			s[i].resize(lim+1);
			s[i][0] = a[i];
		}
		for(int k=1;k<=lim;k++){
			for(int i=0;i+(1<<k)-1<n;i++){
				s[i][k] = max(s[i][k-1] , s[i + (1<<(k-1))][k-1]);
			}
		}
	}
	int query(int l,int r)
	{
		int j = lg[r-l+1];
		return max(s[l][j],s[r-(1<<j)+1][j]);
	}
}mw,mh;
int solve(int i,int j,int k){
	if(dp[k][i].find(j) != dp[k][i].end())return dp[k][i][j];
	if(!k){
		dp[0][i][j] = -1e9;
		int l = j+1,r = w-1;
		while(r>=l){
			int mid = (l+r)/2;
			if(mw.query(j+1,mid) > a[i])r=mid-1;
			else l = mid+1;
		}
		if(l<w)dp[0][i][j] = max(dp[0][i][j],solve(i,l,1) + l - j);
		l = 0;
		r = j-1;
		while(r>=l){
			int mid = (l+r)/2;
			if(mw.query(mid,j-1) > a[i])l = mid+1;
			else r = mid-1;
		}
		if(r>=0)dp[0][i][j] = max(dp[0][i][j],solve(i,r,1) + j - r);
		if(dp[0][i][j] == -1e9)dp[0][i][j] = max(w-1-j,j);
	}else{
		dp[1][i][j] = -1e9;
		int l = i+1,r = h-1;
		while(r>=l){
			int mid = (l+r)/2;
			if(mh.query(i+1,mid) > b[j])r=mid-1;
			else l = mid+1;
		}
		if(l>i && l<h)dp[1][i][j] = max(dp[1][i][j],solve(l,j,0) + l - i);
		l = 0;
		r = i-1;
		while(r>=l){
			int mid = (l+r)/2;
			if(mh.query(mid,i-1) > b[j])l = mid+1;
			else r = mid-1;
		}
		if(r>=0)dp[1][i][j] = max(dp[1][i][j],solve(r,j,0) + i - r);
		if(dp[1][i][j] == -1e9)dp[1][i][j] = max(h-1-i,i);
	}
	return dp[k][i][j];
}
int main()
{
	owo
	cin>>h>>w>>q;
	a.resize(h);
	b.resize(w);
	for(int i=0;i<h;i++)cin>>a[i];
	for(int i=0;i<w;i++)cin>>b[i];
	lg[1] = 0;
	for(int i=2;i<=50000;i++)lg[i] = lg[i/2]+1;
	mh = SPT(h,20,a);
	mw = SPT(w,20,b);
	//mh.print();
	//mw.print();
	while(q--){
		int i,j;
		cin>>i>>j;
		i--;
		j--;
		int ans = max(solve(i,j,0),solve(i,j,1));
		cout<<ans<<'\n';
	}
	
}

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