提出 #67352143

---

ソースコード 拡げる

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int Maxn=1e6+6;
int h,w,k;

struct seg{
    int l,r;
    mutable int id;
    seg(int l=0,int r=0,int id=0):l(l),r(r),id(id){}
    inline friend bool operator <(const seg x,const seg y){
        return x.l<y.l;
    }
};
set<seg>s[Maxn];
int cnt;

vector<int>e[Maxn];
bool vis[Maxn];

void dfs(int u){
    vis[u]=1;
    for(auto v:e[u]){
        if(vis[v]) continue;
        dfs(v);
    }
}

int main(){
    cin>>h>>w>>k;

    for(int i=1;i<=h;i++){
        s[i].insert(seg(1,w,0));
    }
    for(int i=1;i<=k;i++){
        int r,c;
        cin>>r>>c;
        auto it=s[r].upper_bound(seg(c,0,0)); it--;
        int l=(it->l),rr=(it->r); 
        s[r].erase(it);
        if(c>l) s[r].insert(seg(l,c-1,0));
        if(rr>c) s[r].insert(seg(c+1,rr,0));
    }
    for(int i=1;i<=h;i++){
        for(auto &j:s[i]){
            j.id=++cnt;
        }
    }
    for(int i=1;i<h;i++){
        for(auto j:s[i]){
            int l=j.l,r=j.r;
            auto itr=s[i+1].upper_bound(seg(r,0,0)),itl=s[i+1].upper_bound(seg(l,0,0));
            if(itl!=s[i+1].begin()) itl--;
            
            for(auto k=itl;k!=itr;k++){
                if(j.l>k->r or k->l>j.r) continue;
                e[j.id].emplace_back(k->id),e[k->id].emplace_back(j.id);
            } 
        }
    }
    dfs(1);

    if(vis[cnt]) puts("Yes");
    else puts("No");


    return 0;
}

提出情報

ジャッジ結果