oj.uz

Submission #418781

# Submission time Handle Problem Language Result Execution time Memory
418781 2021-06-05T21:27:30 Z MohamedAhmed04 Furniture (JOI20_furniture) C++14
0 / 100
 3 ms 972 KB 
#include <bits/stdc++.h>

using namespace std ;

const int MAX = 1e3 + 10 ;

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

struct Node
{
	int Min = 1e9 , Max = -1e9 ;
};

Node tree[4 * MAX] ;

set<int>s[MAX] ;

Node Merge(Node &a , Node &b)
{
	Node c ; 
	c.Min = min(a.Min , b.Min) ;
	c.Max = max(a.Max , b.Max) ;
	return c ;
}

void update(int node , int l , int r , int idx)
{
	if(idx > r || idx < l)
		return ;
	if(l == r)
	{
		if(s[l].size())
			tree[node].Min = *s[l].begin() , tree[node].Max = *s[l].rbegin() ;
		else
			tree[node].Min = 1e9 , tree[node].Max = -1e9 ;
		return ;
	}
	int mid = (l + r) >> 1 ;
	update(node << 1 , l , mid , idx) ;
	update(node << 1 | 1 , mid+1 , r , idx) ;
	tree[node] = Merge(tree[node << 1] , tree[node << 1 | 1]) ;
}

Node tmp ;

Node query(int node , int l , int r , int from , int to)
{
	if(from > r || to < l || from > to)
		return tmp ;
	if(l >= from && r <= to)
		return tree[node] ;
	int mid = (l + r) >> 1 ;
	Node x = query(node << 1 , l , mid , from , to) ;
	Node y = query(node << 1 | 1 , mid+1 , r , from , to) ;
	return Merge(x , y) ;
}


void upd(int i , int j)
{
	if(arr[i][j-1] == 0 && arr[i+1][j-1] == 1)
	{
		s[i].erase(j-1) ;
		update(1 , 1 , n , i) ;
		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) ;
		update(1 , 1 , n , i-1) ;
		arr[i-1][j] = 1 ;
		upd(i-1 , j) ;
	}
}

bool check(int i , int j)
{
	return (query(1 , 1 , n , i+1 , n).Min < j || query(1 , 1 , n , 1 , i-1).Max > 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) ;
		}
		update(1 , 1 , n , i) ;
	}
	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) ;
			update(1 , 1 , n , i) ;
			upd(i , j) ;
		}
		else
			cout<<0<<"\n" ;
	}
	return 0 ;
}

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 844 KB Output is correct
2 Incorrect 3 ms 972 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 844 KB Output is correct
2 Incorrect 3 ms 972 KB Output isn't correct
3 Halted 0 ms 0 KB -