萌新51分求助!
查看原帖
萌新51分求助!
658786
STUDENT00楼主2022/10/22 09:05

代码如下:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int n,ans,x1[500010],r1[500010];
int ll[500010],rr[500010];
vector<int> vec[500010];
int bfs(int k){
	bool vis[500010]={0};
	queue<int> q;
	q.push(k);
	vis[k]=1;
	int s=0;
	while(!q.empty()){
		int now=q.front();
		s++;
		for(register int i=0;i<vec[now].size();i++){
			if(!vis[vec[now][i]]){
				vis[vec[now][i]]=1;
				q.push(vec[now][i]);
			}
		}
		q.pop();
	}
	return s;
}
signed main(){
	scanf("%lld",&n);
	for(register int i=1;i<=n;i++) scanf("%lld%lld",&x1[i],&r1[i]); 
	int l=1,r=1;
	for(register int i=1;i<=n;i++){
		while(l>1&&x1[i]-x1[l]<=r1[i]) l--;
		while(l<i&&x1[i]-x1[l]>r1[i]) l++;
		while(r>i&&x1[r]-x1[i]>r1[i]) r--;
		while(r<=n&&x1[r]-x1[i]<=r1[i]) r++;
		r--;
		for(register int j=l;j<=r;j++) vec[i].push_back(j);
	}
	for(register int i=1;i<=n;i++) ans=(ans+i*bfs(i)%mod)%mod;
	printf("%lld",ans);
	return 0;
}
2022/10/22 09:05
加载中...