Submission #3433065


Source Code Expand

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#pragma GCC optimize("Ofast,no-stack-protector")
#include <bits/stdc++.h>
#define res register ll
#define lowbit(x) (x&(-x))
#define N 200005
#define inf 0x3f3f3f3f
#define mod 1000000007
#define ll long long
using namespace std;
ll n,m,cnt,a[N],b[N],lisan[N],f[N],ans=1,sum,tot;
inline ll read(){
	res w=0,X=0;register char ch=0;
	while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
	while(isdigit(ch)){X=(X<<1)+(X<<3)+(ch^48);ch=getchar();}
	return w?-X:X;
}
namespace T{
	ll tr[N];
	inline void add(res x,res v){
		for(;x<=cnt;x+=lowbit(x))
		  (tr[x]+=v)%=mod;
	}
	inline ll ask(res x){
		res total=0;
		for(;x;x-=lowbit(x))
		  (total+=tr[x])%=mod;
		return total;
	}
}
struct papa{
	ll x,y;
	inline bool operator<(const papa&b) const{
		return (x==b.x&&y>b.y)||x<b.x;
	}
}p[N];
int main(){
	n=read(),m=read();
	for(res i=1;i<=n;i++)
	  a[i]=read();
	for(res i=1;i<=m;i++)
	  b[i]=read();
	for(res i=1,j=1;i<=n;i++){
		for(;j<=m;j++)
		  if(b[j]>a[i])
		    break;
		if(j==m+1||j==1|| b[j] == a[i]) continue;
		p[++tot].x=b[j]-a[i];
		p[tot].y=a[i]-b[j-1];
    }
	sort(p+1,p+tot+1);
	for(res i=1;i<=tot;i++)
	  lisan[i]=p[i].y;
	sort(lisan+1,lisan+tot+1);
	cnt=unique(lisan+1,lisan+n+1)-lisan;
	for(res i=1;i<=tot;i++)
	  p[i].y=lower_bound(lisan+1,lisan+cnt+1,p[i].y)-lisan;
	for(res i=1;i<=tot;i++){
		if(p[i].x==p[i-1].x&&p[i].y==p[i-1].y) continue;
		sum=(T::ask(p[i].y-1)+1)%mod;
		ans=(ans+sum)%mod;                     
		T::add(p[i].y,sum);
	}
	printf("%lld\n",ans);
	return 0;
}

Submission Info

Submission Time
Task F - Robots and Exits
User miaokehao
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1625 Byte
Status WA
Exec Time 49 ms
Memory 9984 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 900
Status
AC × 5
AC × 59
WA × 2
Set Name Test Cases
Sample 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 0_04.txt
All 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 0_04.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt, 1_46.txt, 1_47.txt, 1_48.txt, 1_49.txt, 1_50.txt, 1_51.txt, 1_52.txt, 1_53.txt, 1_54.txt, 1_55.txt
Case Name Status Exec Time Memory
0_00.txt AC 3 ms 8448 KB
0_01.txt AC 2 ms 8448 KB
0_02.txt AC 2 ms 6400 KB
0_03.txt AC 2 ms 8448 KB
0_04.txt AC 2 ms 8448 KB
1_00.txt AC 2 ms 6400 KB
1_01.txt AC 2 ms 6400 KB
1_02.txt AC 17 ms 9984 KB
1_03.txt AC 14 ms 9088 KB
1_04.txt AC 18 ms 9088 KB
1_05.txt AC 13 ms 8960 KB
1_06.txt AC 14 ms 8960 KB
1_07.txt AC 17 ms 8960 KB
1_08.txt AC 23 ms 9984 KB
1_09.txt AC 23 ms 9984 KB
1_10.txt WA 23 ms 9984 KB
1_11.txt AC 22 ms 9984 KB
1_12.txt AC 22 ms 9984 KB
1_13.txt AC 22 ms 9984 KB
1_14.txt AC 23 ms 9984 KB
1_15.txt WA 23 ms 9984 KB
1_16.txt AC 49 ms 9984 KB
1_17.txt AC 48 ms 9984 KB
1_18.txt AC 48 ms 9984 KB
1_19.txt AC 48 ms 9984 KB
1_20.txt AC 47 ms 9984 KB
1_21.txt AC 49 ms 9984 KB
1_22.txt AC 48 ms 9984 KB
1_23.txt AC 48 ms 9984 KB
1_24.txt AC 11 ms 6400 KB
1_25.txt AC 11 ms 6400 KB
1_26.txt AC 10 ms 6400 KB
1_27.txt AC 10 ms 6400 KB
1_28.txt AC 19 ms 9472 KB
1_29.txt AC 12 ms 8576 KB
1_30.txt AC 11 ms 8576 KB
1_31.txt AC 22 ms 9728 KB
1_32.txt AC 15 ms 8832 KB
1_33.txt AC 23 ms 9344 KB
1_34.txt AC 22 ms 9344 KB
1_35.txt AC 25 ms 9728 KB
1_36.txt AC 16 ms 8960 KB
1_37.txt AC 20 ms 9344 KB
1_38.txt AC 22 ms 9472 KB
1_39.txt AC 19 ms 9088 KB
1_40.txt AC 27 ms 9600 KB
1_41.txt AC 33 ms 9984 KB
1_42.txt AC 31 ms 9728 KB
1_43.txt AC 28 ms 9600 KB
1_44.txt AC 39 ms 9984 KB
1_45.txt AC 39 ms 9984 KB
1_46.txt AC 38 ms 9984 KB
1_47.txt AC 39 ms 9984 KB
1_48.txt AC 42 ms 9984 KB
1_49.txt AC 42 ms 9984 KB
1_50.txt AC 42 ms 9984 KB
1_51.txt AC 42 ms 9984 KB
1_52.txt AC 45 ms 9984 KB
1_53.txt AC 44 ms 9984 KB
1_54.txt AC 44 ms 9984 KB
1_55.txt AC 44 ms 9984 KB