Submission #233002

#TimeUsernameProblemLanguageResultExecution timeMemory
233002thebesAbduction 2 (JOI17_abduction2)C++14
44 / 100
5050 ms18676 KiB
#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>,int> 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]){ // horizontal line 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{ // vertical line 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); dp.clear(); 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("%d\n",sna); } return 0; }

Compilation message (stderr)

abduction2.cpp: In function 'int main()':
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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...