AtCoder Grand Contest 015 E - Mr.Aoki Incubator

题目传送门：https://agc015.contest.atcoder.jp/tasks/agc015_e

题目大意：

数轴上有\(N\)个点，每个点初始时在位置\(X_i\)，以\(V_i\)的速度向数轴正方向前进

初始时刻，你可以选择一些点为其染色，之后的行走过程中，染色的点会将其碰到的所有点都染上色，之后被染上色的点亦是如此

在所有\(2^N\)种初始染色方案中，问有多少种初始染色方案，能使得最终所有的点都被染色？答案对\(10^9+7\)取模

我们考虑按速度排序，对于每个点\(i\)，我们找到最左边的\(L\)满足\(x_L\geqslant x_i\)，找到最右边的\(R\)满足\(x_R\leqslant x_i\)，那么\(i\)被染色后，\([L,R]\)都会被染色，而且我们可以得知，染色的区间不会互相包含

这样问题就转变为了由一堆区间覆盖线段的方案数，我们用单调队列优化DP即可

/*program from Wolfycz*/

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define inf 0x7f7f7f7f

#define min(x,y) (x<y?x:y)

#define max(x,y) (x>y?x:y)

using namespace std;

typedef long long ll;

typedef unsigned int ui;

typedef unsigned long long ull;

inline char gc(){

	static char buf[1000000],*p1=buf,*p2=buf;

	return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;

}

inline int frd(){

	int x=0,f=1; char ch=gc();

	for (;ch<'0'||ch>'9';ch=gc())	if (ch=='-')	f=-1;

	for (;ch>='0'&&ch<='9';ch=gc())	x=(x<<3)+(x<<1)+ch-'0';

	return x*f;

}

inline int read(){

	int x=0,f=1; char ch=getchar();

	for (;ch<'0'||ch>'9';ch=getchar())	if (ch=='-')	f=-1;

	for (;ch>='0'&&ch<='9';ch=getchar())	x=(x<<3)+(x<<1)+ch-'0';

	return x*f;

}

inline void print(int x){

	if (x<0)	putchar('-'),x=-x;

	if (x>9)	print(x/10);

	putchar(x%10+'0');

}

const int N=2e5,p=1e9+7;

struct S1{

	int x,v;

	void rd(){x=read(),v=read();}

	bool operator <(const S1 &tis)const{return v<tis.v;}

}A[N+10];

struct S2{

	int l,r;

	void insert(int _l,int _r){l=_l,r=_r;}

	bool operator <(const S2 &tis)const{return r!=tis.r?r<tis.r:l<tis.l;}

}v[N+10];

int stack[N+10],top;

int s[N+10],f[N+10];

int main(){

	int n=read();

	for (int i=1;i<=n;i++)	A[i].rd();

	sort(A+1,A+1+n);

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

		if (!top||A[i].x>A[stack[top]].x)	stack[++top]=i;

		int l=1,r=top;

		while (l<=r){

			int mid=(l+r)>>1;

			if (A[i].x<=A[stack[mid]].x)	r=mid-1;

			else	l=mid+1;

		}

		v[i].l=stack[l];

	}

	top=0;

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

		if (!top||A[i].x<A[stack[top]].x)	stack[++top]=i;

		int l=1,r=top;

		while (l<=r){

			int mid=(l+r)>>1;

			if (A[stack[mid]].x<=A[i].x)	r=mid-1;

			else	l=mid+1;

		}

		v[i].r=stack[l];

	}

	sort(v+1,v+1+n);

	int now=1,Ans=0;

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

		while (v[now].r<v[i].l-1)	now++;

		f[i]=(s[i-1]-s[now-1]+p)%p;

		if (v[i].l==1)	f[i]++;

		if (v[i].r==n)	Ans=(Ans+f[i])%p;

		s[i]=(s[i-1]+f[i])%p;

	}

	printf("%d\n",Ans);

	return 0;

}

巴特西

AtCoder Grand Contest 015 E - Mr.Aoki Incubator

最新文章

热门文章