Submission #287420

#	Time	Username	Problem	Language	Result	Execution time	Memory
287420		TadijaSebez	Abduction 2 (JOI17_abduction2)	C++11	100 / 100	2265 ms	133624 KiB

abduction2

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define ll long long
const int N=50050;
const int L=16;
int a[N],b[N],lgs[N];
struct SparseTable{
	int rmq[N][L],n;
	SparseTable(){}
	void Build(int*a,int n){
		this->n=n;
		for(int i=1;i<=n;i++)rmq[i][0]=a[i];
		for(int j=1;j<L;j++){
			for(int i=1;i<=n-(1<<j)+1;i++){
				rmq[i][j]=max(rmq[i][j-1],rmq[i+(1<<j-1)][j-1]);
			}
		}
	}
	int Get(int l,int r){
		int k=lgs[r-l+1];
		return max(rmq[l][k],rmq[r-(1<<k)+1][k]);
	}
	pii GetRng(int x,int y){
		int top=x-1,bot=1,mid,L=0,R=n+1;
		while(top>=bot){
			mid=top+bot>>1;
			if(Get(mid,x-1)>y)L=mid,bot=mid+1;
			else top=mid-1;
		}
		top=n,bot=x+1;
		while(top>=bot){
			mid=top+bot>>1;
			if(Get(x+1,mid)>y)R=mid,top=mid-1;
			else bot=mid+1;
		}
		return {L,R};
	}
}A,B;
int n,m,q;
map<pii,ll> dp[2];
ll DP(int x,int y,int t){
	if(x<1||x>n||y<1||y>m)return -1;
	if(dp[t].count({x,y}))return dp[t][{x,y}];
	ll ans;
	if(t==0){
		pii rng=A.GetRng(x,b[y]);
		//printf("1: %i %i -> %i %i\n",x,y,rng.first,rng.second);
		ans=max(DP(rng.first,y,1)+x-rng.first,DP(rng.second,y,1)+rng.second-x);
	}else{
		pii rng=B.GetRng(y,a[x]);
		//printf("2: %i %i -> %i %i\n",x,y,rng.first,rng.second);
		ans=max(DP(x,rng.first,0)+y-rng.first,DP(x,rng.second,0)+rng.second-y);
	}
	return dp[t][{x,y}]=ans;
}
int main(){
	for(int i=2;i<N;i++)lgs[i]=lgs[i>>1]+1;
	scanf("%i %i %i",&n,&m,&q);
	for(int i=1;i<=n;i++)scanf("%i",&a[i]);A.Build(a,n);
	for(int i=1;i<=m;i++)scanf("%i",&b[i]);B.Build(b,m);
	while(q--){
		int x,y;
		scanf("%i %i",&x,&y);
		printf("%lld\n",max(DP(x,y,0),DP(x,y,1)));
	}
	return 0;
}

Compilation message (stderr)

abduction2.cpp: In member function 'void SparseTable::Build(int*, int)':
abduction2.cpp:16:42: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   16 |     rmq[i][j]=max(rmq[i][j-1],rmq[i+(1<<j-1)][j-1]);
      |                                         ~^~
abduction2.cpp: In member function 'std::pair<int, int> SparseTable::GetRng(int, int)':
abduction2.cpp:27:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |    mid=top+bot>>1;
      |        ~~~^~~~
abduction2.cpp:33:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |    mid=top+bot>>1;
      |        ~~~^~~~
abduction2.cpp: In function 'int main()':
abduction2.cpp:60:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   60 |  for(int i=1;i<=n;i++)scanf("%i",&a[i]);A.Build(a,n);
      |  ^~~
abduction2.cpp:60:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   60 |  for(int i=1;i<=n;i++)scanf("%i",&a[i]);A.Build(a,n);
      |                                         ^
abduction2.cpp:61:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   61 |  for(int i=1;i<=m;i++)scanf("%i",&b[i]);B.Build(b,m);
      |  ^~~
abduction2.cpp:61:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   61 |  for(int i=1;i<=m;i++)scanf("%i",&b[i]);B.Build(b,m);
      |                                         ^
abduction2.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |  scanf("%i %i %i",&n,&m,&q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~
abduction2.cpp:60:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   60 |  for(int i=1;i<=n;i++)scanf("%i",&a[i]);A.Build(a,n);
      |                       ~~~~~^~~~~~~~~~~~
abduction2.cpp:61:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |  for(int i=1;i<=m;i++)scanf("%i",&b[i]);B.Build(b,m);
      |                       ~~~~~^~~~~~~~~~~~
abduction2.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |   scanf("%i %i",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~~

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