LINK:Greater and Greater

确实没能想到做法。

考虑利用bitset解决问题。

做法是:逐位判断每一位是否合法 第一位 就是 bitset上所有大于\(b_1\)的位置 置为1.

那么右移一位就得到下次判断的东西 然后 处理处相应>=\(b_2\)的东西 然后再&一下。

这样复杂度为\(\frac{nm}{w}\) w取64 所以可以通过.

不过值得一提的是 预处理的那个东西不能全部预处理出来 因为这样做 空间复杂度是\(\frac{nm}{w}\)的会爆掉。

直接维护\(ans_i\)表示以i开头是否合法 那么对于每次一个p位置的判定 所有为1的位置得到之后我们能反推出以某个位置为起点的是合法的 &一下即可。

这样就不需要那么大空间了。

code
//#include<bits\stdc++.h>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<string>
#include<ctime>
#include<cmath>
#include<cctype>
#include<cstdlib>
#include<queue>
#include<deque>
#include<stack>
#include<vector>
#include<algorithm>
#include<utility>
#include<bitset>
#include<set>
#include<map>
#define ll long long
#define db double
#define INF 10000000000000000ll
#define ldb long double
#define pb push_back
#define put_(x) printf("%d ",x);
#define get(x) x=read()
#define gt(x) scanf("%d",&x)
#define gi(x) scanf("%lf",&x)
#define put(x) printf("%d\n",x)
#define putl(x) printf("%lld\n",x)
#define gc(a) scanf("%s",a+1)
#define rep(p,n,i) for(RE int i=p;i<=n;++i)
#define go(x) for(int i=lin[x],tn=ver[i];i;tn=ver[i=nex[i]])
#define fep(n,p,i) for(RE int i=n;i>=p;--i)
#define vep(p,n,i) for(RE int i=p;i<n;++i)
#define pii pair<int,int>
#define mk make_pair
#define RE register
#define P 1000000007
#define gf(x) scanf("%lf",&x)
#define pf(x) ((x)*(x))
#define uint unsigned long long
#define ui unsigned
#define EPS 1e-4
#define sq sqrt
#define S second
#define F first
#define mod 1000000007
#define V vector<int>
#define l(x) t[x].l
#define r(x) t[x].r
#define sum(x) t[x].sum
#define cnt(x) t[x].cnt
using namespace std;
char buf[1<<15],*fs,*ft;
inline char getc()
{
return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
}
inline int read()
{
RE int x=0,f=1;RE char ch=getc();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();}
return x*f;
}
const int MAXN=150010,maxn=40010;
bitset<MAXN>ans,w;
int a[MAXN],b[maxn];
int c[MAXN],p[MAXN];
int n,m;
inline int cmp1(int x,int y){return a[x]>a[y];}
inline int cmp2(int x,int y){return b[x]>b[y];}
int main()
{
freopen("1.in","r",stdin);
get(n);get(m);
rep(1,n,i)get(a[i]),p[i]=i;
rep(1,m,i)get(b[i]),c[i]=i;
sort(p+1,p+1+n,cmp1);
sort(c+1,c+1+m,cmp2);
int flag=1;
ans.set();
rep(1,m,i)
{
while(a[p[flag]]>=b[c[i]]&&flag<=n)
{
w[p[flag]]=1;
++flag;
}
ans=ans&(w>>c[i]-1);
}
put(ans.count());return 0;
}

最新文章

  1. C# 文件下载 : WebClient
  2. yii2 配置文件加载顺序, 以及调用自定义配置信息。
  3. bzoj1188 [HNOI2007]分裂游戏 博弈论 sg函数的应用
  4. CSS3动画(性能篇)
  5. linux 快捷键
  6. 【STL】-迭代器的用法
  7. sublime远程连接到linux主机
  8. Andy Williams 《Love Story》
  9. Unity中的CG编写Shader系列(Blend)
  10. modal verbs(一)
  11. Easyui 修改|新增jquery-easyui icon图标
  12. ITextSharp构造PDF文件
  13. VS调试dll详细过程记录
  14. uniGUI 通过SessionList操作另外的登录用户
  15. 使用Synchronized块同步变量
  16. $.ajax dataType设置为json 回调函数不执行
  17. 使用threejs点云秀出酷炫的图片效果(一)
  18. Codeforces Round #358 (Div. 2) C. Alyona and the Tree 水题
  19. An example of using Pandas for regression
  20. crontab定时运行python脚本访问MySQL遇到问题

热门文章

  1. rpm部分命令解读
  2. POJ2393贪心
  3. django模板中变更数据库信息后,如何把变更后的信息同步更新到数据库
  4. Jetbranis学习资料之全家桶
  5. day4 python 运算符
  6. 三个Python自动化测试高效工具的使用总结
  7. 一位Google高管审查了20,000+简历,他发现了这5个致命的错误
  8. p70_域名解析系统DNS
  9. JAVA集合四:比较器--类自定义排序
  10. Java集合框架1-- HashMap