oj.uz

Submission #538576

# Submission time Handle Problem Language Result Execution time Memory
538576 2022-03-17T07:10:31 Z rrrr10000 Furniture (JOI20_furniture) C++14
100 / 100
 386 ms 20064 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<bool> vb;
typedef vector<vb> vvb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define pb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
const ll mod=1000000007;
const ll inf=1001001001001;
ll modpow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    ll n,m;cin>>n>>m;
    vvi v(n,vi(m));
    rep(i,n)rep(j,m)cin>>v[i][j];
    vvb s(n,vb(m,true)),t(n,vb(m,true));
    queue<P> que;
    vi dx={1,0,0,-1},dy={0,1,-1,0};
    vi cnt(n+m-1,inf);
    auto sols=[&](){
        while(!que.empty()){
            auto x=que.front();que.pop();
            rep(k,2){
                P nx(x.fi+dx[k],x.se+dy[k]);
                if(nx.fi<n&&nx.se<m&&s[nx.fi][nx.se]){
                    P nnx(nx.fi-dx[1-k],nx.se-dy[1-k]);
                    if(nnx.fi>=0&&nnx.se>=0&&s[nnx.fi][nnx.se])continue;
                    if(t[nx.fi][nx.se])cnt[nx.fi+nx.se]--;
                    assert(cnt[nx.fi+nx.se]>0);
                    s[nx.fi][nx.se]=false;que.emplace(nx);
                }
            }
        }
    };
    auto solt=[&](){
        while(!que.empty()){
            auto x=que.front();que.pop();
            REP(k,2,4){
                P nx(x.fi+dx[k],x.se+dy[k]);
                if(nx.fi>=0&&nx.se>=0&&t[nx.fi][nx.se]){
                    P nnx(nx.fi-dx[5-k],nx.se-dy[5-k]);
                    if(nnx.fi<n&&nnx.se<m&&t[nnx.fi][nnx.se])continue;
                    if(s[nx.fi][nx.se])cnt[nx.fi+nx.se]--;
                    assert(cnt[nx.fi+nx.se]>0);
                    t[nx.fi][nx.se]=false;que.emplace(nx);
                }
            }
        }
    };
    rep(i,n)rep(j,m)if(v[i][j]){
        s[i][j]=false;que.emplace(i,j);
    }sols();
    rep(i,n)rep(j,m)if(v[i][j]){
        t[i][j]=false;que.emplace(i,j);
    }solt();
    rep(i,n+m-1)cnt[i]=0;
    rep(i,n)rep(j,m)if(s[i][j]&&t[i][j])cnt[i+j]++;
    // outvv(s);
    // outvv(t);
    // outv(cnt);
    ll q;cin>>q;
    rep(qq,q){
        ll x,y;cin>>x>>y;x--;y--;
        if(s[x][y]&&t[x][y]&&cnt[x+y]==1)out(0);
        else{
            out(1);
            if(s[x][y]&&t[x][y])cnt[x+y]--;
            s[x][y]=false;que.emplace(x,y);sols();
            t[x][y]=false;que.emplace(x,y);solt();
        }
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 4 ms 468 KB Output is correct
8 Correct 4 ms 468 KB Output is correct
9 Correct 4 ms 468 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 4 ms 468 KB Output is correct
8 Correct 4 ms 468 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 13 ms 1160 KB Output is correct
11 Correct 3 ms 460 KB Output is correct
12 Correct 184 ms 13672 KB Output is correct
13 Correct 73 ms 11132 KB Output is correct
14 Correct 313 ms 17940 KB Output is correct
15 Correct 297 ms 16920 KB Output is correct
16 Correct 318 ms 18372 KB Output is correct
17 Correct 376 ms 19484 KB Output is correct
18 Correct 366 ms 19008 KB Output is correct
19 Correct 382 ms 20064 KB Output is correct
20 Correct 352 ms 20024 KB Output is correct
21 Correct 386 ms 20008 KB Output is correct