求助!! WA on #1 #2 86pts
查看原帖
求助!! WA on #1 #2 86pts
510378
binyufang楼主2023/12/21 23:26
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<queue>
#include<vector>
#include<map>

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

const int INF=0x3f3f3f3f, N=3e6+10, M=N*21, mod=1e9+7;
const double eps=1e-6, PI=acos(-1);

int n, pos[N], tot, lft[N], rit[N];
bool st[N];
ll a[N], b[N];
PII dt[N];
struct Edge
{
	int v, nxt;
}e[M], e1[M];
int h[N], ecnt, h1[N], ecnt1;
map<PII, int> mp;
ll f[N];

struct Seg_Tree
{
	int u, l, r;
}tr[M];

void add(int u,int v)
{
	e[ecnt].nxt=h[u], e[ecnt].v=v, h[u]=ecnt++;
}

void add1(int u,int v)
{
	e1[ecnt1].nxt=h1[u], e1[ecnt1].v=v, h1[u]=ecnt1++;
}

void build(int u,int l,int r)
{
	tr[u]=(Seg_Tree){u, l, r};
	tot=max(tot, u);
	if (l==r)
	{
		pos[l]=u;
		return ;
	}
	int mid=l+r>>1;
	build(u<<1, l, mid), build(u<<1|1, mid+1, r);
	add(u, u<<1), add(u, u<<1|1);
}

void modify(int u,int l,int r,int ql,int qr,int x)
{
	if (ql<=l && r<=qr)
	{
		if (pos[x]==u) return ;
		add(pos[x], u); return ;
	}
	int mid=l+r>>1;
	if (ql<=mid) modify(u<<1, l, mid, ql, qr, x);
	if (qr>mid) modify(u<<1|1, mid+1, r, ql, qr, x);
}

int dfn[N], low[N], stk[N], top, scc, id[N], dfs_cnt;
bool in_stk[N];
void tarjan(int u)
{
    dfn[u]=low[u]=++dfs_cnt;
    stk[++top]=u,in_stk[u]=true;
    
    for (int i=h[u];i!=-1;i=e[i].nxt)
    {
        int v=e[i].v;
        if (!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if (in_stk[v]) low[u]=min(low[u],dfn[v]);
    }
    
    if (dfn[u]==low[u])
    {
        int y;
        scc++;
        
        do
        {
            y=stk[top--];
            in_stk[y]=false;
            lft[scc]=min(lft[scc], dt[y].first);
            rit[scc]=max(rit[scc], dt[y].second);
            id[y]=scc;
        } while (y!=u);
    }
}

void dfs(int u)
{
	st[u]=true;
	for (int i=h1[u];i!=-1;i=e1[i].nxt)
	{
		int v=e1[i].v;
		if (st[v]) continue;
		dfs(v);
		lft[v]=min(lft[u], lft[v]);
		rit[v]=max(rit[u], rit[v]);
	}
}

int main()		
{
	cin>>n;
	memset(h, -1, sizeof(h));
	for (int i=1;i<=n;i++)
	{
		cin>>a[i]>>b[i];
	}
	
	build(1, 1, n);
	memset(lft, 0x3f, sizeof(lft));
	for (int i=1;i<=n;i++)
	{
		int l=lower_bound(a+1, a+n+1, a[i]-b[i])-a;
		int r=upper_bound(a+1, a+n+1, a[i]+b[i])-a-1;
		modify(1, 1, n, l, r, i);
		dt[pos[i]]=(PII){l, r};
	}
	for (int i=1;i<=tot;i++) if (!dt[i].first) dt[i].first=INF, dt[i].second=-1;
	for (int i=1;i<=tot;i++) 
	{
		if (!dfn[i]) tarjan(i); 
	}
	memset(h1, -1, sizeof(h1));
	for (int x=1;x<=tot;x++)
	{
		for (int j=h[x];j!=-1;j=e[j].nxt)
		{		
			int y=e[j].v;
			if (id[x]==id[y]) continue;
			if (mp[(PII){id[y], id[x]}]) continue;
			mp[(PII){id[y], id[x]}]=1;
			add1(id[y], id[x]);
		}
	}
	
	for (int i=1;i<=scc;i++)
	{
		if (!st[i]) dfs(i);
	}
	
	ll res=0;
	for (int i=1;i<=n;i++)
	{
		int t=id[pos[i]];
		int len=rit[t]-lft[t]+1;
		res=(res+i*len)%mod;
	}
	cout<<res<<endl;
	return 0;
}
2023/12/21 23:26
加载中...