Submission #364504

#	Time	Username	Problem	Language	Result	Execution time	Memory
364504		ronnith	Furniture (JOI20_furniture)	C++14	100 / 100	422 ms	23788 KiB

furniture

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using tiii = tuple<int, int, int>;
using ld = long double;

#define all(a) (a).begin(), (a).end()
#define sz(a) int((a).size())
#define pb push_back
#define eb emplace_back

#define mk make_pair
#define mt make_tuple
#define f first
#define s second

template<class T> void maxself(T& x, T y){x = (y > x ? y : x);}
template<class T> void minself(T& x, T y){x = (y < x ? y : x);}

const ld PI = 3.141592653589793238462643;
const ll mod = 1000000007;
struct mi{
	ll val;explicit operator int() const {return val;}
	mi():val(0){}
	mi(ll v):val(v % mod){}
};
mi operator+(mi a, mi b){return (a.val + b.val) % mod;}
mi operator*(mi a, mi b){return (a.val * b.val) % mod;}
mi operator-(mi a, mi b){return (a.val - b.val + mod) % mod;}

const int N = 1000;
int n, m, q, a[N][N], mr[2][N][N], fr[2*N-1];

void cor1(int i, int j) {
	if(a[i][j] == 0) return;
	int res = 0;
	if(i != n - 1 && a[i + 1][j]) res = 1;
	if(j != m - 1 && a[i][j + 1]) res = 1;
	a[i][j] = res;
	if(!res) {
		fr[i + j] --;
		if(i != 0) cor1(i - 1, j);
		if(j != 0) cor1(i, j - 1);
	}
}

void cor2(int i, int j) {
	if(a[i][j] == 0) return;
	int res = 0;
	if(i != 0 && a[i - 1][j]) res = 1;
	if(j != 0 && a[i][j - 1]) res = 1;
	a[i][j] = res;
	if(!res) {
		fr[i + j] --;
		if(i != n - 1) cor2(i + 1, j);
		if(j != m - 1) cor2(i, j + 1);
	}
}

void solve() {
	cin >> n >> m;

	for(int i = 0;i < n;i ++) 
		for(int j = 0;j < m;j ++) 
			cin >> a[i][j];

	for(int i = 0;i < n;i ++) 
		for(int j = 0;j < m;j ++) 
			if(i == 0 && j == 0) {
				mr[0][i][j] = 1;
			} else {
				mr[0][i][j] = 0;
				if(i > 0 && mr[0][i - 1][j]) mr[0][i][j] = 1;
				if(j > 0 && mr[0][i][j - 1]) mr[0][i][j] = 1;
				if(a[i][j] == 1) mr[0][i][j] = 0;
			}

	for(int i = n - 1;i >= 0;i --) 
		for(int j = m - 1;j >= 0;j --) 
			if(i == n - 1 && j == m - 1) {
				mr[1][i][j] = 1;
			} else {
				mr[1][i][j] = 0;
				if(i < n - 1 && mr[1][i + 1][j]) mr[1][i][j] = 1;
				if(j < m - 1 && mr[1][i][j + 1]) mr[1][i][j] = 1;
				if(a[i][j] == 1) mr[1][i][j] = 0;
			}

	for(int i = 0;i < n;i ++) { 
		for(int j = 0;j < m;j ++) {
			a[i][j] = (mr[0][i][j] && mr[1][i][j]);
			if(a[i][j]) fr[i + j] ++;
		//	cerr << a[i][j] << ' ';
		}
	//	cerr << '\n';
	}

	cin >> q;
	while(q --) {

		int x, y; cin >> x >> y; x --,y --;

		if(a[x][y] == 0) {
			cout << 1 << '\n';
			continue;
		}

		if(fr[x + y] == 1) {
			cout << 0 << '\n';
		} else {
			cout << 1 << '\n';
			a[x][y] = 0;
			fr[x + y] --;
			if(x != 0)
				cor1(x - 1, y);
			if(y != 0)
				cor1(x, y - 1);
			if(x != n - 1)
				cor2(x + 1, y);
			if(y != m - 1)
				cor2(x, y + 1);

		//	for(int i = 0;i < n;i ++) {
		//		for(int j = 0;j < m;j ++) 
		//			cerr << a[i][j] << ' ';
		//		cerr << '\n';
		//	}

		}

	}

}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int T = 1;
	while(T --) solve();

}

/*

X if we have a set of blocks which can be part of a path for the coressponding diagnol.
CORRECT mark wether this block can be reached.

CASE 1 : 
	chaning one can disconnect it it is the only point in the diagnol.
	if it is so then do nothing.

CASE 2 : 
	it can be marked.
	use recursive function to check mark other changes.	

*/

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