oj.uz

답안 #418785

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
418785 2021-06-05T21:35:33 Z MohamedAhmed04 Furniture (JOI20_furniture) C++14
0 / 100
 2 ms 844 KB 
#include <bits/stdc++.h>

using namespace std ;

const int MAX = 1e3 + 10 ;

int arr[MAX][MAX] ;
int n , m ;

set<int>s[MAX] ;

void upd(int i , int j)
{
	if(arr[i][j-1] == 0 && arr[i+1][j-1] == 1)
	{
		s[i].erase(j-1) ;
		arr[i][j-1] = 1 ;
		upd(i , j-1) ;
	}
	if(arr[i-1][j] == 0 && arr[i-1][j+1] == 1)
	{
		s[i-1].erase(j) ;
		arr[i-1][j] = 1 ;
		upd(i-1 , j) ;
	}
}

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

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>m ;
	for(int i = 0 ; i <= n+1 ; ++i)
	{
		for(int j = 0 ; j <= m+1 ; ++j)
			arr[i][j] = 1 ;
	}
	for(int i = 1 ; i <= n ; ++i)
	{
		for(int j = 1 ; j <= m ; ++j)
			cin>>arr[i][j] ;
	}
	for(int i = 1 ; i <= n ; ++i)
	{
		for(int j = 1 ; j <= m ; ++j)
		{
			if(arr[i][j] == 0)
				s[i].insert(j) ;
		}
	}
	for(int i = n ; i >= 1 ; --i)
	{
		for(int j = m ; j >= 1 ; --j)
		{
			if(arr[i][j] == 1)
				upd(i , j) ;
		}
	}
	int q ;
	cin>>q ;
	while(q--)
	{
		int i , j ;
		cin>>i>>j ;
		if(arr[i][j] == 1)
			cout<<1<<"\n" ;
		else if(check(i , j))
		{
			cout<<1<<"\n" ;
			arr[i][j] = 1 , s[i].erase(j) ;
			upd(i , j) ;
		}
		else
			cout<<0<<"\n" ;
	}
	return 0 ;
}

Subtask #1
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 844 KB Output is correct
2 Incorrect 2 ms 844 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 95.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 844 KB Output is correct
2 Incorrect 2 ms 844 KB Output isn't correct
3 Halted 0 ms 0 KB -