oj.uz

Submission #441426

# Submission time Handle Problem Language Result Execution time Memory
441426 2021-07-05T07:23:13 Z zaneyu Furniture (JOI20_furniture) C++14
100 / 100
 345 ms 18900 KB 
/*input
2 3
0 0 1
0 0 0
3
2 2
2 1
1 2
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast,unroll-loops")
//order_of_key #of elements less than x
// find_by_order kth element
using ll=long long;
using ld=long double;
using pii=pair<int,int>;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()),c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
const ll INF64=1e18+1;
const int INF=0x3f3f3f3f;
int MOD=1e9+7;
const ld PI=acos(-1);
const ld eps=1e-3;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
inline ll mult(ll a,ll b){
    if(a>=MOD) a%=MOD;
    if(b>=MOD) b%=MOD;
    return (a*b)%MOD;
}
inline ll mypow(ll a,ll b){
    if(b<=0) return 1;
    ll res=1LL;
    while(b){
        if(b&1) res=mult(res,a);
        a=mult(a,a);
        b>>=1;
    }
    return res;
}
const int maxn=1e3+5;
const int maxlg=__lg(maxn)+2;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
bool vs[maxn][maxn],ve[maxn][maxn];
bool ok[maxn][maxn];
int cnt[2*maxn];
int arr[maxn][maxn];
int n,m;
bool isin(int x,int y){
    if(x<1 or x>n or y<1 or y>m) return false;
    return true;
}
bool bad(int x,int y){
    if(x==1 and y==1) return false;
    if(x==n and y==m) return false;
    if(!ok[x-1][y] and !ok[x][y-1]) return true;
    if(!ok[x][y+1] and !ok[x+1][y]) return true;
    return false;
}
int32_t main(){
    ios::sync_with_stdio(false),cin.tie(0);
    cin>>n>>m;
    REP1(i,n) REP1(j,m){
        cin>>arr[i][j];
    }
    queue<pii> q;
    q.push({1,1});
    vs[1][1]=1;
    while(!q.empty()){
        pii z=q.front();
        q.pop();
        if(z.f<n and !arr[z.f+1][z.s] and !vs[z.f+1][z.s]) vs[z.f+1][z.s]=1,q.push({z.f+1,z.s});
        if(z.s<m and !arr[z.f][z.s+1] and !vs[z.f][z.s+1]) vs[z.f][z.s+1]=1,q.push({z.f,z.s+1});
    }
    q.push({n,m});
    ve[n][m]=1;
    while(!q.empty()){
        pii z=q.front();
        q.pop();
        if(z.f>1 and !arr[z.f-1][z.s] and !ve[z.f-1][z.s]) ve[z.f-1][z.s]=1,q.push({z.f-1,z.s});
        if(z.s>1 and !arr[z.f][z.s-1] and !ve[z.f][z.s-1]) ve[z.f][z.s-1]=1,q.push({z.f,z.s-1});
    }
    REP1(i,n){
        REP1(j,m){
            if(vs[i][j] and ve[i][j]) ok[i][j]=1,cnt[i+j]++;
        }
    }
    int qq;
    cin>>qq;
    while(qq--){
        int x,y;
        cin>>x>>y;
        if(!ok[x][y]) cout<<"1\n";
        else{
            if(cnt[x+y]>1){
                ok[x][y]=0;
                cnt[x+y]--;
                cout<<"1\n";   
                q.push({x,y});
                while(!q.empty()){
                    pii z=q.front();
                    q.pop();
                    REP(k,4){
                        int nx=z.f+dx[k],ny=z.s+dy[k];
                        if(isin(nx,ny) and bad(nx,ny) and ok[nx][ny]){
                            ok[nx][ny]=0;
                            cnt[nx+ny]--;
                            q.push({nx,ny});
                        }
                    }
                }
                
            }
            else cout<<"0\n";
        }
        //REP1(i,n) REP1(j,m) cout<<ok[i][j]<<' ';
    }
}

Subtask #1
5.0 / 5.0

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

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 2 ms 972 KB Output is correct
3 Correct 2 ms 972 KB Output is correct
4 Correct 3 ms 972 KB Output is correct
5 Correct 4 ms 972 KB Output is correct
6 Correct 4 ms 972 KB Output is correct
7 Correct 4 ms 972 KB Output is correct
8 Correct 4 ms 972 KB Output is correct
9 Correct 4 ms 972 KB Output is correct
10 Correct 10 ms 716 KB Output is correct
11 Correct 4 ms 716 KB Output is correct
12 Correct 208 ms 11836 KB Output is correct
13 Correct 90 ms 8680 KB Output is correct
14 Correct 297 ms 16220 KB Output is correct
15 Correct 343 ms 16476 KB Output is correct
16 Correct 312 ms 17400 KB Output is correct
17 Correct 331 ms 18312 KB Output is correct
18 Correct 333 ms 17936 KB Output is correct
19 Correct 344 ms 18768 KB Output is correct
20 Correct 331 ms 18772 KB Output is correct
21 Correct 345 ms 18900 KB Output is correct