能到达吗

C++14(g++5.4) 解法, 执行用时: 757ms, 内存消耗: 50612K, 提交时间: 2020-04-18 21:56:11

#include<bits/stdc++.h>
using namespace std;
const int M=3e6+5;
const int P=1e9+7;

int n,m,K;

struct conot
{
    int x,y;
    bool operator <(const conot &b)const
    {
        if(x!=b.x)return x<b.x;
        return y<b.y;
    }
}A[M];

struct node{int x,l,r;}B[M];int tot;

void Make_B()
{
    sort(A+1,A+K+1);tot=0;
    for(int i=1;i<=K;i++)
    {
        if(i==1 || A[i].x!=A[i-1].x){if(A[i].y>1)B[++tot]=(node){A[i].x,1,A[i].y-1};}
        else{if(i!=1 && A[i].y>A[i-1].y+1)B[++tot]=(node){A[i].x,A[i-1].y+1,A[i].y-1};}
        if(i==K || A[i].x!=A[i+1].x){if(A[i].y<m)B[++tot]=(node){A[i].x,A[i].y+1,m};}
    }
}

int fa[M];long long siz[M];int getfa(int u){return fa[u]?fa[u]=getfa(fa[u]):u;}
void Merge(int u,int v)
{
    u=getfa(u),v=getfa(v);
    if(u==v)return;
    siz[v]+=siz[u];fa[u]=v;
}
int Id[M];
int Vec[M],vc;set<int>S;
bool cmp(int x,int y){return B[x].l<B[y].l;}
void Solve()
{
    Make_B();
    for(int i=1;i<=tot;i++)fa[i]=0,siz[i]=B[i].r-B[i].l+1;
    S.clear();for(int i=1;i<=K;i++)S.insert(A[i].x);
    A[0].x=0;A[K+1].x=n+1;
    int tot2=tot;
    for(int i=1;i<=K+1;i++)if(A[i].x>A[i-1].x+1)
    {
        ++tot2;
        Id[A[i].x-1]=Id[A[i-1].x+1]=tot2;
        fa[tot2]=0;siz[tot2]=1ll*m*(A[i].x-A[i-1].x-1);
    }
    for(int i=1;i<=tot;i++)
    {
        if(B[i].x>1 && !S.count(B[i].x-1))Merge(i,Id[B[i].x-1]);
        if(B[i].x<n && !S.count(B[i].x+1))Merge(i,Id[B[i].x+1]);
        if(i>1 && B[i].x==B[i-1].x+1)
        {
            vc=0;
            for(int j=i-1;j>=1 && B[j].x==B[i-1].x;j--)Vec[++vc]=j;
            for(int j=i;j<=tot && B[j].x==B[i].x;j++)Vec[++vc]=j;
            sort(Vec+1,Vec+vc+1,cmp);
            int Mx=B[Vec[1]].r;
            for(int j=2;j<=vc;j++)
            {
                if(B[Vec[j]].l<=Mx)Merge(Vec[j-1],Vec[j]);
                Mx=max(Mx,B[Vec[j]].r);
            }
        }
    }
    long long Ans=0;
    for(int i=1;i<=tot2;i++)
        if(getfa(i)==i)
            siz[i]%=P,(Ans+=siz[i]*(siz[i]+1)%P*500000004)%=P;
    printf("%lld\n",Ans);
}

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&m,&K);
        for(int i=1;i<=K;i++)scanf("%d%d",&A[i].x,&A[i].y);
        Solve();
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 179ms, 内存消耗: 29148K, 提交时间: 2020-04-18 14:48:50

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define For(a,b,c) for(int a=b;a<=c;++a)
#define Dor(a,b,c) for(int a=b;a>=c;--a)
using namespace std;
typedef long long LL;
bool m1;
char buf[10000005],*p1=buf,*p2=buf;
#define Getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,10000000,stdin),p1==p2)?EOF:*p1++)
void rd(int &x) {
    x=0; char c=Getchar();
    while(!isdigit(c)) c=Getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=Getchar();
}
const int N=1000007,M=3000007,P=1000000007;
struct O {
	int x,y;
	bool operator < (const O &_) const {
		if(x!=_.x) return x<_.x;
		return y<_.y;
	}
}A[N];
struct L {
	int l,r,i;
}F[N],G[N];
int a,b,n,f,g,C[M],S[M];
int fi(int u) {
	return u==C[u]?u:C[u]=fi(C[u]);
}
void uni(int x,int y) {
	x=fi(x),y=fi(y);
	if(x!=y) C[x]=y,(S[y]+=S[x])%=P;
}
void mrg() {
	int u=1;
	For(v,1,f) {
		while(u<=g&&G[u].r<=F[v].r) {
			if(G[u].r>=F[v].l) uni(G[u].i,F[v].i);
			++u;
		}
		if(u<=g&&G[u].l<=F[v].r&&G[u].r>=F[v].l) uni(G[u].i,F[v].i);
	}
	For(i,1,f) G[i]=F[i];
	g=f,f=0;
}
void magic() {
	rd(a),rd(b),rd(n),f=g=0;
	For(i,1,n) rd(A[i].x),rd(A[i].y);
	sort(A+1,A+1+n);
	int c=0;
	For(i,1,n) {
		int j=i,l=1;
		while(j<n&&A[j+1].x==A[j].x) ++j;
		if(A[i].x!=A[i-1].x+1) {
			F[f=1]=(L){1,b,++c},S[c]=1LL*(A[i].x-A[i-1].x-1)*b%P,C[c]=c;
			mrg();
		}
		For(k,i,j) {
			if(l<=A[k].y-1) F[++f]=(L){l,A[k].y-1,++c},S[c]=F[f].r-F[f].l+1,C[c]=c;
			l=A[k].y+1;
		}
		if(l<=b) F[++f]=(L){l,b,++c},S[c]=F[f].r-F[f].l+1,C[c]=c;
//		For(k,1,f) printf("[%d,%d]\n",F[k].l,F[k].r);
		mrg();
		i=j;
	}
	if(A[n].x<a) {
		F[f=1]=(L){1,b,++c},S[c]=1LL*(a-A[n].x)*b%P,C[c]=c;
		mrg();
	}
	int ans=0;
	For(i,1,c) {
		if(fi(i)!=i) continue;
		ans=(ans+1LL*S[i]*(S[i]+1)/2)%P;
	}
	printf("%d\n",ans);
}
bool m2;
int main() {
//	cerr<<(&m2-&m1)/1048576.<<"MB"<<endl;
	int T;
	rd(T);
	while(T--) magic();
	return 0;
}

详情