結果

問題 No.3369 Find MyakuMyaku
コンテスト
ユーザー Naru820
提出日時 2025-11-16 05:23:02
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 363 ms / 2,000 ms
コード長 3,843 bytes
コンパイル時間 3,760 ms
コンパイル使用メモリ 308,952 KB
実行使用メモリ 28,032 KB
最終ジャッジ日時 2025-11-17 20:48:17
合計ジャッジ時間 13,397 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define rep(i,s,n) for (int i = (int)(s); i < (int)(n); i++)
#define reb(i,s,n) for (int i = (int)(n)-1; i >= (int)(s); i--)
#define all(v) begin(v), end(v)
using namespace std;
using ll = long long;
bool chmin(auto &a, auto b) { return a > b ? a = b, 1 : 0; }
bool chmax(auto &a, auto b) { return a < b ? a = b, 1 : 0; }

const vector<int> dx = {1,0,-1,0};
const vector<int> dy = {0,1,0,-1};

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &a){
    if (a.empty()) return os;
    os << a.front();
    for (auto e : a | views::drop(1)){
        os << ' ' << e;
    }
    return os;
}

void dump(auto ...vs){
    ((cout << vs << ' '), ...) << endl;
}

#include<atcoder/lazysegtree>
using pii = pair<int,int>;

pii op(pii a, pii b){
    return min(a,b);
}
pii e(){
    return {1e9,1e9};
}
pii mapping(int f, pii x){
    x.first += f;
    return x;
}
int composition(int f, int g){
    return f + g;
}
int ident(){
    return 0;
}

void solve(){
    int n, h, w; cin >> n >> h >> w;
    vector<tuple<int,int,int,int>> recs(n);
    rep(i,0,n){
        int lx, rx, ly, ry; cin >> lx >> rx >> ly >> ry; rx++, ry++;
        //int lx, rx, ly, ry; cin >> lx >> ly >> rx >> ry; rx++, ry++;
        recs[i] = {lx,rx,ly,ry};
    }
    using dty = atcoder::lazy_segtree<pii,op,e,int,mapping,composition,ident>;
    vector<dty> ds(h+2);
    {
        vector imos(h+3,vector<int>(w+3));
        for (auto [lx, rx, ly, ry] : recs){
            imos[lx][ly]++;
            imos[lx][ry]--;
            imos[rx][ly]--;
            imos[rx][ry]++;
        }
        rep(i,0,h+2) rep(j,0,w+3){
            imos[i+1][j] += imos[i][j];
        }
        rep(i,0,h+3) rep(j,0,w+2){
            imos[i][j+1] += imos[i][j];
        }
        rep(i,0,h+2){
            ds[i] = dty([&]{
                vector<pii> a(w+2);
                rep(j,0,w+2){
                    a[j] = {imos[i][j],j};
                }
                return a;
            }());
        }
    }
    int wcnt = 0;
    vector white(h+2,vector<bool>(w+2,false));
    vector done(h+2,vector<bool>(w+2,false));
    queue<pair<int,int>> que;
    auto add_white = [&](){
        rep(x,0,h+2){
            while (ds[x].all_prod().first == 0){
                int y = ds[x].all_prod().second;
                white[x][y] = true;
                wcnt++;
                ds[x].set(y,e());
                bool ok = false;
                rep(k,0,4){
                    int nx = x + dx[k];
                    int ny = y + dy[k];
                    if (0 <= nx && nx < h+2 && 0 <= ny && ny < w+2){
                        if (done[nx][ny]){
                            ok = true;
                        }
                    }
                }
                if (ok){
                    done[x][y] = true;
                    que.emplace(x,y);
                }
            }
        }
    };
    add_white();
    assert(white[h+1][w+1]);
    que.emplace(h+1,w+1);
    done[h+1][w+1] = true;
    int vis = 0;
    vector<bool> ans(n);
    reb(i,0,n){
        while (!que.empty()){
            auto [x, y] = que.front(); que.pop();
            vis++;
            rep(k,0,4){
                int nx = x + dx[k];
                int ny = y + dy[k];
                if (0 <= nx && nx < h+2 && 0 <= ny && ny < w+2){
                    if (!done[nx][ny] && white[nx][ny]){
                        done[nx][ny] = true;
                        que.emplace(nx,ny);
                    }
                }
            }
        }
        assert(wcnt >= vis);
        ans[i] = (wcnt != vis);
        auto [lx, rx, ly, ry] = recs[i];
        rep(x,lx,rx){
            ds[x].apply(ly,ry,-1);
        }
        add_white();
    }
    rep(i,0,n){
        cout << (ans[i] ? "Yes" : "No") << '\n';
    }
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    solve();
}
0