This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef vector<int> vi;
#define F first
#define S second
#define pb push_back
#define mt make_tuple
const int MN = 1e5+5;
int N, M, Q, i, j, x, y, dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
map<tuple<int,int,int>,ll> dp; vi a, b;
struct MaxSegmentTree{
int st[2*MN], n;
void build(int i,int s,int e,vi &vec){
if(s!=e){
build(2*i,s,(s+e)/2,vec);
build(2*i+1,(s+e)/2+1,e,vec);
st[i]=max(st[2*i],st[2*i+1]);
}
else st[i]=vec[s];
}
void init(vi vec){
n = (int)vec.size();
build(1,0,n-1,vec);
}
int lquery(int i,int s,int e,int ss,int se,int val){
if(ss>se) return -1;
if(s>=ss&&e<=se){
if(st[i]<=val) return -1;
else if(s==e) return e;
}
else if((s+e)/2<ss) return lquery(2*i+1,(s+e)/2+1,e,ss,se,val);
else if((s+e)/2>=se) return lquery(2*i,s,(s+e)/2,ss,se,val);
int r = lquery(2*i+1,(s+e)/2+1,e,ss,se,val);
return r==-1?lquery(2*i,s,(s+e)/2,ss,se,val):r;
}
int lquery(int idx,int val){
return lquery(1,0,n-1,0,idx-1,val);
}
int rquery(int i,int s,int e,int ss,int se,int val){
if(ss>se) return -1;
if(s>=ss&&e<=se){
if(st[i]<=val) return -1;
else if(s==e) return s;
}
else if((s+e)/2<ss) return rquery(2*i+1,(s+e)/2+1,e,ss,se,val);
else if((s+e)/2>=se) return rquery(2*i,s,(s+e)/2,ss,se,val);
int r = rquery(2*i,s,(s+e)/2,ss,se,val);
return r==-1?rquery(2*i+1,(s+e)/2+1,e,ss,se,val):r;
}
int rquery(int idx,int val){
return rquery(1,0,n-1,idx+1,n,val);
}
}R,C;
int solve(int x,int y,int d){
if(dp.count(mt(x,y,d))) return dp[mt(x,y,d)];
int ans = 0;
if(a[x]>b[y]){
if(d!=0){
int nxt = C.lquery(y,a[x]);
if(~nxt) ans=max(ans,y-nxt+solve(x,nxt,1));
else ans=max(ans,y);
}
if(d!=1){
int nxt = C.rquery(y,a[x]);
if(~nxt) ans=max(ans,nxt-y+solve(x,nxt,0));
else ans=max(ans,M-1-y);
}
}
else{
if(d!=2){
int nxt = R.lquery(x,b[y]);
if(~nxt) ans=max(ans,x-nxt+solve(nxt,y,3));
else ans=max(ans,x);
}
if(d!=3){
int nxt = R.rquery(x,b[y]);
if(~nxt) ans=max(ans,nxt-x+solve(nxt,y,2));
else ans=max(ans,N-1-x);
}
}
return dp[mt(x,y,d)]=ans;
}
int main(){
scanf("%d%d%d",&N,&M,&Q);
for(i=1;i<=N;i++){
scanf("%d",&x);
a.pb(x);
}
for(i=1;i<=M;i++){
scanf("%d",&x);
b.pb(x);
}
R.init(a), C.init(b);
for(;Q;Q--){
scanf("%d%d",&x,&y);
int sna = 0;
for(i=0;i<4;i++){
int nx=x+dx[i], ny=y+dy[i];
if(nx<1||nx>N||ny<1||ny>M) continue;
sna=max(sna,solve(nx-1,ny-1,i)+1);
}
printf("%lld\n",sna);
}
return 0;
}
Compilation message (stderr)
abduction2.cpp: In function 'int main()':
abduction2.cpp:110:28: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
printf("%lld\n",sna);
^
abduction2.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&N,&M,&Q);
~~~~~^~~~~~~~~~~~~~~~~~~
abduction2.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&x);
~~~~~^~~~~~~~~
abduction2.cpp:98:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&x);
~~~~~^~~~~~~~~
abduction2.cpp:103:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&x,&y);
~~~~~^~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |