Submission #624805

#TimeUsernameProblemLanguageResultExecution timeMemory
624805CSQ31Abduction 2 (JOI17_abduction2)C++17
100 / 100
729 ms139888 KiB
#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; typedef long long int ll; const int MAXN = 5e4+5; vector<int>a,b; int h,w,q; map<int,ll>dp[2][MAXN]; int lg[MAXN]; struct spt{ vector<int>a; vector<vector<int>>mx; int n; spt(){} spt(vector<int>_a){ a = _a; n = a.size(); mx.resize(20); for(int i=0;i<20;i++)mx[i].assign(n,-1e9); for(int i=0;i<n;i++)mx[0][i] = a[i]; for(int i=1;i<20;i++){ for(int j=0;j+(1<<i)-1<n;j++){ mx[i][j] = max(mx[i-1][j],mx[i-1][j+(1<<(i-1))]); } } } int query(int l,int r){ int v = lg[r-l+1]; int res = max(mx[v][l],mx[v][r-(1<<v)+1]); return res; } void print(){ for(int i=0;i<20;i++){ for(int j=0;j+(1<<i)-1<n;j++)cout<<mx[i][j]<<" "; cout<<'\n'; } } }mw,mh; ll solve(ll i,ll j,ll k){ if(dp[k][i].find(j) != dp[k][i].end())return dp[k][i][j]; if(!k){ dp[0][i][j] = -1e9; ll l = j+1,r = w-1; while(r>=l){ ll 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); else dp[0][i][j] = max(dp[0][i][j],w-1-j); l = 0; r = j-1; while(r>=l){ ll 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); else dp[0][i][j] = max(dp[0][i][j],j); }else{ dp[1][i][j] = -1e9; ll l = i+1,r = h-1; while(r>=l){ ll mid = (l+r)/2; if(mh.query(i+1,mid) > b[j])r=mid-1; else l = mid+1; } if(l<h)dp[1][i][j] = max(dp[1][i][j],solve(l,j,0) + l - i); else dp[1][i][j] = max(dp[1][i][j],l-1-i); l = 0; r = i-1; while(r>=l){ ll 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); else dp[1][i][j] = max(dp[1][i][j],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(a); mw = spt(b); //mh.print(); //mw.print(); while(q--){ int i,j; cin>>i>>j; i--; j--; ll ans = max(solve(i,j,0),solve(i,j,1)); cout<<ans<<'\n'; } }
#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...