Submission #702231

#	Time	Username	Problem	Language	Result	Execution time	Memory
702231		fadi57	Furniture (JOI20_furniture)	C++14	100 / 100	1915 ms	63080 KiB

furniture

#include<bits/stdc++.h>
using namespace std;
const int mx=1e3 + 10;

int dx[4]= {0,0,1,-1};
int dy[4]= {-1,1,0,0};
const int mod=998244353;
typedef long long ll;

int n,m;
set<int>ok[mx];
int c[mx][mx];
void goo(int x,int y)
{
    if(c[x-1][y]==0&&c[x-1][y+1]==1)
    {
        ok[x-1].erase(y) ;
        c[x-1][y] = 1 ;
        goo(x-1, y) ;

    }

    if(c[x][y-1]==0&&c[x+1][y-1]==1)
    {
        ok[x].erase(y-1) ;
        c[x][y-1] = 1 ;
        goo(x, y-1) ;

    }


    if(c[x][y+1]==0&&c[x-1][y+1]==1)
    {
        ok[x].erase(y+1) ;
        c[x][y+1] = 1 ;
        goo(x, y+1) ;

    }


    if(c[x+1][y]==0&&c[x+1][y-1]==1)
    {
        ok[x+1].erase(y) ;
        c[x+1][y] = 1 ;
        goo(x+1, y) ;

    }
}


bool check(int i,int j)
{

    int x = 1e9, y = -1e9 ;
    if(ok[i+1].size())
        x = *ok[i+1].begin() ;
    if(ok[i-1].size())
        y = *ok[i-1].rbegin() ;
    return (x < j || y > j) ;


}
void solve()
{
    //  cout<<(1<<4);
    cin>>n>>m;
    for(int i=0; i<=n+1; i++)
    {
        for(int j=0; j<=m+1; j++)
        {
            c[i][j]=1;
        }
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            cin>>c[i][j];
        }
    }

    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            if(c[i][j]==0)
            {
                ok[i].insert(j) ;
            }

        }


    }
    for(int i = n ; i >= 1 ; --i)
	{
		for(int j = m ; j >= 1 ; --j)
		{
			if(c[i][j] == 1)
				goo(i , j) ;
		}
	}
    int q ;
    cin>>q ;
    while(q--)
    {
        int i, j ;
        cin>>i>>j ;
        if(c[i][j] == 1)
            cout<<1<<"\n" ;
        else if(check(i, j))
        {
            cout<<1<<"\n" ;
            c[i][j] = 1, ok[i].erase(j) ;
            goo(i, j) ;
        }
        else
            cout<<0<<"\n" ;
    }


}


int main()


{
solve();

    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95