G-Greater and Greater 2020牛客多校第二场
程序员文章站
2022-04-02 19:02:26
...
https://ac.nowcoder.com/acm/contest/5667/G
我透这题30多个人过了,我们队蛤不清be
ccpc2016合肥补题的时候补过一个bitset,这里没想起来,知道要用bitset后也想不到怎么做。。。太菜了
对a和b从大到小排序
ans维护以每个位置为起点,如果可以全部si>bi,就为1
那么从大到小枚举b,然后用一个bitset f,记录当前大于等于b的有哪些位,由于从大到小枚举,那么之前大于等于bi的,也大于等于b_{i+1},而对于第bi.id位,用ans&=f>>bi.id就可以把那些匹配bi.id位不行的起点的ans全部变成0
最后答案就是还剩多少个起点依然是1
#include<bits/stdc++.h>
using namespace std;
const int maxl=2e5+10;
typedef pair<int,int> p;
int n,m;
struct node
{
int val,id;
}a[maxl],b[maxl];
bitset<150010> f,ans;
inline bool cmp(const node &x,const node &y)
{
return x.val>y.val;
}
inline void prework()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i].val),a[i].id=i;
for(int i=1;i<=m;i++)
scanf("%d",&b[i].val),b[i].id=i;
sort(a+1,a+1+n,cmp);
sort(b+1,b+1+m,cmp);
}
inline void mainwork()
{
ans.set();f.reset();
int j=0;
for(int i=1;i<=m;i++)
{
while(j+1<=n && a[j+1].val>=b[i].val)
f[a[++j].id]=1;
ans=ans&(f>>b[i].id);
}
}
inline void print()
{
printf("%d",ans.count());
}
int main()
{
prework();
mainwork();
print();
return 0;
}
推荐阅读
-
2020牛客多校第三场-J Just Shuffle
-
2020牛客多校第3场[Clam and Fish+贪心]
-
2020牛客多校第三场 E Two Matchings
-
2020牛客暑期多校训练营(第二场)Cover the Tree
-
2020牛客暑期多校 第一场 F Infinite String Comparision(字符串)
-
【2020牛客多校】第九场 K The Flee Plan of Groundhog——BFS
-
2020牛客多校第八场 K
-
I 1 or 2 2020牛客暑期多校第一场
-
2020牛客暑期多校训练营(第二场)C Cover the Tree
-
2020暑假牛客多校训练营第二场