题解：AT_abc391_d [ABC391D] Gravity

The_jester_from_Lst · 2025-02-02 11:34:06 · 题解

真有这么多大佬卡这题？

考虑怎么判方块 i 在 a 时刻是否存在。我们可以模拟一遍方块掉落的过程，预处理出每个方块对应的掉落的时间，则查询时只需判断这个时间与 a 的大小关系即可。

考虑如何模拟方块掉落的过程。对于 1 到 w 每一个 x 维护一个按 y 降序的 vector，记为 g_i。则每一次一起掉落的一定是每个 g_i 的末尾的元素，即每个 x 对应最低的 y。至于掉落时间，则是这些元素中 y 的最大值。因为一定要最后一排都齐了才能掉落。那么我们直接模拟这个过程即可。

特别的，如果过程中发现有一个 g_i 为空，即有一个 x 上的方块已经掉完了，则剩下的方块不可能被消除了，直接退出即可。

模拟过程中每个方块至多访问 2 遍，复杂度为排序的 O(n\log n)。

附上代码：

#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;
}