Educational Codeforces Round 105 (Rated for Div. 2) C. 1D Sokoban

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=2e5+10;
 4 const int mod=1e9+7;
 5 #define ll long long
 6 #define ull unsigned long long
 7 #define pi pair<int,int>
 8 #define fi first
 9 #define sc second
10 #define pb push_back
11 int n,m;
12 int a[maxn],b[maxn];
13 int c[maxn],d[maxn];
14 int suf[maxn];
15 int lenc,lend;
16 
17 int solve()
18 {
19     map<int,int>mp;
20     for(int i=1;i<=lenc;i++) mp[c[i]]=1;
21     for(int i=lend;i>=1;i--) suf[i]=suf[i+1]+mp[d[i]];
22 
23     int ans=suf[1];
24     for(int i=1;i<=lend;i++)
25     {
26         int p1=upper_bound(c+1,c+1+lenc,d[i])-c;
27         p1--;
28 
29         int p2=lower_bound(d+1,d+1+lend,d[i]-p1+1)-d;
30         int sum=i-p2+1+suf[i+1];
31         //cout<<sum<<" "<<i<<‘\n‘;
32         ans=max(ans,sum);
33     }
34     return ans;
35 }
36 
37 
38 
39 int main()
40 {
41     ios::sync_with_stdio(0);
42     cin.tie(0);
43     int t;
44     cin>>t;
45     while(t--)
46     {
47         cin>>n>>m;
48         for(int i=1;i<=n;i++) cin>>a[i];
49         for(int i=1;i<=m;i++) cin>>b[i];
50         int ans=0;
51 
52         lenc=0,lend=0;
53         for(int i=1;i<=n;i++) if(a[i]>0) c[++lenc]=a[i];
54         for(int i=1;i<=m;i++) if(b[i]>0) d[++lend]=b[i];
55         for(int i=1;i<=max(n,m)+1;i++) suf[i]=0;
56         ans+=solve();
57 
58         lenc=0,lend=0;
59         for(int i=n;i>=1;i--) if(a[i]<0) c[++lenc]=-a[i];
60         for(int i=m;i>=1;i--) if(b[i]<0) d[++lend]=-b[i];
61         for(int i=1;i<=max(n,m)+1;i++) suf[i]=0;
62         ans+=solve();
63 
64         cout<<ans<<‘\n‘;
65     }
66 
67 
68 
69 
70 
71 
72 }