oj.uz

Submission #683781

# Submission time Handle Problem Language Result Execution time Memory
683781 2023-01-19T10:51:56 Z Fysty Furniture (JOI20_furniture) C++17
100 / 100
 231 ms 15792 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define MottoHayaku ios::sync_with_stdio(false);cin.tie(0);
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define F first
#define S second
#define pb push_back

const int N=1005;
int n,m;
bool has[N][N],can[N][N],dp[N][N],vis[N][N];
int cnt[N*2];
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
queue<pii> q;
void check(int x,int y)
{
    if(x<1||x>n||y<1||y>m) return;
    if(vis[x][y]) return;
    bool bad=0;
    if((x>1||y>1)&&dp[x-1][y]==0&&dp[x][y-1]==0) bad=1;
    if((x<n||y<m)&&dp[x+1][y]==0&&dp[x][y+1]==0) bad=1;
    //cout<<x<<" "<<y<<" bad?"<<bad<<"\n";
    if(bad)
    {
        vis[x][y]=1;
        dp[x][y]=0;
        cnt[x+y]--;
        q.push({x,y});
    }
}
signed main()
{
    MottoHayaku
    cin>>n>>m;
    rep1(i,n) rep1(j,m) cin>>has[i][j];
    rep1(i,n) rep1(j,m) dp[i][j]=1;
    can[1][1]=1;
    rep1(i,n)
    {
        rep1(j,m)
        {
            if(i>1||j>1) can[i][j]=can[i-1][j]|can[i][j-1];
            can[i][j]&=(!has[i][j]);
            dp[i][j]&=can[i][j];
        }
    }
    rep1(i,n) rep1(j,m) can[i][j]=0;
    can[n][m]=1;
    for(int i=n;i>=1;i--)
    {
        for(int j=m;j>=1;j--)
        {
            if(i<n||j<m) can[i][j]=can[i+1][j]|can[i][j+1];
            can[i][j]&=(!has[i][j]);
            dp[i][j]&=can[i][j];
        }
    }
    rep1(i,n) rep1(j,m)
    {
        //cout<<i<<" "<<j<<" "<<dp[i][j]<<"\n";
        if(dp[i][j]==0)
        {
            vis[i][j]=1;
            q.push({i,j});
        }
        else cnt[i+j]++;
    }
    int Q;
    cin>>Q;
    while(Q--)
    {
        int x,y;
        cin>>x>>y;
        while(!q.empty())
        {
            int tx=q.front().F,ty=q.front().S;
            //cout<<tx<<" "<<ty<<"\n";
            q.pop();
            rep(d,4) check(tx+dx[d],ty+dy[d]);
        }
        if(!dp[x][y]) cout<<"1\n";
        else
        {
            if(cnt[x+y]==1) cout<<"0\n";
            else
            {
                cout<<"1\n";
                dp[x][y]=0;
                vis[x][y]=1;
                cnt[x+y]--;
                q.push({x,y});
            }
        }
    }
}

Subtask #1
5.0 / 5.0

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

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 3 ms 724 KB Output is correct
8 Correct 3 ms 724 KB Output is correct
9 Correct 4 ms 728 KB Output is correct
10 Correct 8 ms 1236 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 161 ms 10268 KB Output is correct
13 Correct 69 ms 8624 KB Output is correct
14 Correct 200 ms 14700 KB Output is correct
15 Correct 231 ms 13660 KB Output is correct
16 Correct 215 ms 14580 KB Output is correct
17 Correct 223 ms 15364 KB Output is correct
18 Correct 231 ms 14964 KB Output is correct
19 Correct 227 ms 15744 KB Output is correct
20 Correct 229 ms 15760 KB Output is correct
21 Correct 227 ms 15792 KB Output is correct