题解：AT_abc391_d [ABC391D] Gravity

~~真有这么多大佬卡这题？~~

考虑怎么判方块

i

在

a

时刻是否存在。我们可以模拟一遍方块掉落的过程，预处理出每个方块对应的掉落的时间，则查询时只需判断这个时间与

a

的大小关系即可。

考虑如何模拟方块掉落的过程。对于

1

到

w

每一个

x

维护一个按

y

降序的

vector

，记为

g_i

。则每一次一起掉落的一定是每个

g_i

的末尾的元素，即每个

x

对应最低的

y

。至于掉落时间，则是这些元素中

y

的最大值。因为一定要最后一排都齐了才能掉落。那么我们直接模拟这个过程即可。

特别的，如果过程中发现有一个

g_i

为空，即有一个

x

上的方块已经掉完了，则剩下的方块不可能被消除了，直接退出即可。

模拟过程中每个方块至多访问

2

遍，复杂度为排序的

O(n\log n)

。

附上代码：

CPP

#include<bits/stdc++.h>
#define int long long
#define il inline
#define pii pair<int,int>
#define mk make_pair
#define fir first
#define sec second
#define pb emplace_back
#define mod 1000000007
#define put putchar
using namespace std;
il int rd(){
    int jya=0,tl=1;char jyt=getchar();
    while(!isdigit(jyt)){if(jyt=='-')tl=-1;jyt=getchar();}
    while(isdigit(jyt)){jya=(jya<<1)+(jya<<3)+(jyt-'0');jyt=getchar();}
    return jya*tl;
}
il void wr(int jjy){
    if(jjy<0)putchar('-'),jjy=-jjy;
    if(jjy>9)wr(jjy/10);
    putchar(jjy%10+48);
}
const int JYAAKIOI=1e18,N=1e6+86,M=5e3+86;
struct node{
	int x,y,id;
}a[N];
int n,w,q,t,id,ed[N],nn;
vector<pii>g[N];
il bool cmp(node x,node y){
	if(x.x==y.x)return x.y>y.y;
	return x.x<y.x;
}
il void init(){
	while(1){
		int maxt=0;
		for(int i=1;i<=w;++i){
			if(!g[i].size()){
				maxt=-1;
				break;
			}
			maxt=max(maxt,g[i][g[i].size()-1].fir);
		}
		//cout<<maxt<<endl;
		if(maxt==-1)break;
		for(int i=1;i<=w;++i){
			ed[g[i][g[i].size()-1].sec]=maxt;
			g[i].pop_back();
		}
	}
}
signed main(){
	n=rd();w=rd();nn=n;
	for(int i=1;i<=n;++i)a[i].x=rd(),a[i].y=rd(),a[i].id=i;
	memset(ed,-1,sizeof ed);
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;++i)g[a[i].x].pb(mk(a[i].y,a[i].id));
	/*for(int i=1;i<=n;++i){
		cout<<i<<":   ";
		for(auto j:g[i]){
			cout<<j.fir<<' ';
		}
		cout<<endl;
	}*/
	init();
	//for(int i=1;i<=n;++i)cout<<ed[i]<<endl;
	q=rd();
	while(q--){
		t=rd(),id=rd();
		if(ed[id]<=t&&ed[id]!=-1)puts("No");
		else puts("Yes");
	}
    return 0;
}

题解：AT_abc391_d [ABC391D] Gravity

文章操作

相关推荐

评论

题解：AT_abc391_d [ABC391D] Gravity