#2255. 「SNOI2017」炸弹

题目描述

在一条直线上有 NNN 个炸弹，每个炸弹的坐标是 XiX_iXi，爆炸半径是 RiR_iRi，当一个炸弹爆炸时，如果另一个炸弹所在位置 XjX_jXj 满足：

Xi−Ri≤Xj≤Xi+Ri X_i-R_i\leq X_j \leq X_i+R_iXi−Ri≤Xj≤Xi+Ri

那么，该炸弹也会被引爆。

现在，请你帮忙计算一下，先把第 iii 个炸弹引爆，将引爆多少个炸弹呢？

输入格式

第一行，一个数字 NNN，表示炸弹个数。第 2∼N+12\sim N+12∼N+1 行，每行 222 个数字，表示 XiX_iXi，RiR_iRi，保证 XiX_iXi 严格递增。

输出格式

一个数字，表示 ∑i=1ni×\sum \limits_{i=1}^n i\timesi=1∑ni× 炸弹 iii 能引爆的炸弹个数 mod109+7。

样例

样例输入

样例输出

样例解释

炸弹 1,2,3,41,2,3,41,2,3,4 分别能引爆 1,3,3,41,3,3,41,3,3,4 个炸弹，所以答案是 1×1+2×3+3×3+4×4=321\times 1+2\times 3+3\times 3+4\times 4=321×1+2×3+3×3+4×4=32。

数据范围与提示

20%20\%20% 的数据：N≤100N\leq 100N≤100
50%50\%50% 的数据：N≤1000N\leq 1000N≤1000
80%80\%80% 的数据：N≤100000N\leq 100000N≤100000
100%100\%100% 的数据：N≤500000N\leq 500000N≤500000，−1018≤Xi≤1018-10^{18}\leq X_i\leq 10^{18}−1018≤Xi≤1018，0≤Ri≤2×10180\leq R_i\leq 2\times 10^{18}0≤Ri≤2×1018

数据范围与原题相同，但测试数据由本站会员自制，并非原数据。
时限已按照评测机速度调整，原题时限为2000ms，省选评测时调整为4000ms，这里按4000ms调整。

原题评测环境为Windows，栈空间2MB。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#define maxn 1010

#define mod 1000000007

using namespace std;

long long X[maxn],R[maxn];

int n,head[maxn],num;

bool vis[maxn];

struct node{int to,pre;}e[maxn*maxn];

void Insert(int from,int to){

    e[++num].to=to;

    e[num].pre=head[from];

    head[from]=num;

}

long long qread(){

    long long i=,j=;

    char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')j=-;ch=getchar();}

    while(ch<=''&&ch>=''){i=i*+ch-'';ch=getchar();}

    return i*j;

}

int bfs(int x){

    int res=;

    memset(vis,,sizeof(vis));

    queue<int>q;q.push(x);vis[x]=;

    while(!q.empty()){

        int now=q.front();q.pop();

        for(int i=head[now];i;i=e[i].pre){

            int to=e[i].to;

            if(!vis[to]){

                res++;

                vis[to]=;

                q.push(to);

            }

        }

    }

    return res;

}

int main(){

    n=qread();

    for(int i=;i<=n;i++)X[i]=qread(),R[i]=qread();

    for(int i=;i<=n;i++){

        for(int j=i-;j>=;j--){

            if(X[i]-R[i]<=X[j])Insert(i,j);

            else break;

        }

        for(int j=i+;j<=n;j++){

            if(X[i]+R[i]>=X[j])Insert(i,j);

            else break;

        }

    }

    int ans=;

    for(int i=;i<=n;i++){

        int num=bfs(i);

        ans=(ans+1LL*i*num%mod)%mod;

    }

    printf("%d",ans);

}

50分暴力

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#define maxn 500010

#define mod 1000000007

using namespace std;

long long X[maxn],R[maxn];

int n,l[maxn],r[maxn],ans;

long long qread(){

    long long i=,j=;

    char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')j=-;ch=getchar();}

    while(ch<=''&&ch>=''){i=i*+ch-'';ch=getchar();}

    return i*j;

}

int main(){

    n=qread();

    for(int i=;i<=n;i++)X[i]=qread(),R[i]=qread();

    for(int i=;i<=n;i++){

        l[i]=i;

        while(l[i]>&&X[i]-X[l[i]-]<=R[i])

            l[i]=l[l[i]-],R[i]=max(R[i],R[l[i]]-X[i]+X[l[i]]);

    }

    for(int i=n;i>=;i--){

        r[i]=i;

        while(r[i]<n&&X[r[i]+]-X[i]<=R[i])

            r[i]=r[r[i]+],l[i]=min(l[i],l[r[i]]);

    }

    for(int i=;i<=n;i++)ans=(ans+1LL*i*(r[i]-l[i]+)%mod)%mod;

    printf("%d",ans);

    return ;

}

100分

炸弹

loj #2255. 「SNOI2017」炸弹