[nowcoder5667G]Greater and Greater

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 150005
 4 struct ji{
 5     int k,id;
 6     bool operator < (const ji &a)const{
 7         return (k<a.k)||(k==a.k)&&(id<a.id);
 8     }
 9 }a[N];
10 int n,m,ans,b[N];
11 bitset<40005>o,s,g[40005];
12 void write(bitset<40005> o){
13     for(int i=1;i<=m;i++){
14         int x=o[i];
15         printf("%d ",x);
16     }
17     printf("\n");
18 }
19 int main(){
20     scanf("%d%d",&n,&m);
21     for(int i=1;i<=n;i++)scanf("%d",&b[i]);
22     for(int i=1;i<=m;i++){
23         scanf("%d",&a[i].k);
24         a[i].id=i;
25     }
26     sort(a+1,a+m+1);
27     g[1][0]=1;
28     for(int i=1,j=1;i<=m;i=j){
29         while (a[i].k==a[j].k)j++;
30         g[j]=g[i];
31         for(int k=i;k<j;k++)g[j][a[k].id]=1;
32     }
33     o[0]=s[0]=1;
34     for(int i=1;i<=n;i++){
35         s=(((s<<1)|o)&g[upper_bound(a+1,a+m+1,ji{b[i],m+1})-a]);
36         if (s[m]==1)ans++;
37     }
38     printf("%d",ans);
39 }