Submission #623112

#	Time	Username	Problem	Language	Result	Execution time	Memory
623112		S2speed	Furniture (JOI20_furniture)	C++17	100 / 100	1091 ms	113536 KiB

furniture

#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize ("Ofast")

#define sze(x) (ll)(x.size())
typedef long long ll;
typedef pair<ll , ll> pll;

const ll maxn = 1e3 + 17 , maxv = 1e6 + 17;

ll n , m;
set<ll> r[maxn] , c[maxn];
bitset<maxn> a[maxn] , z[maxn] , b[maxn];
vector<pll> v;

void del(ll i , ll j){
	if(!a[i][j]) return;
	v.clear();
	v.push_back({i , j});
	a[i][j] = false;
	ll x = 0;
	while(x < sze(v)){
		ll i = v[x].first , j = v[x++].second;
		r[i].erase(j); c[j].erase(i);
		if(i < n - 1){
			if(a[i + 1][j]){
				if(j == 0){
					a[i + 1][j] = z[i + 1][j] = false;
					v.push_back({i + 1 , j});
				} else {
					if(!a[i + 1][j - 1]){
						a[i + 1][j] = z[i + 1][j] = false;
						v.push_back({i + 1 , j});
					}
				}
			}
		}
		if(j < m - 1){
			if(a[i][j + 1]){
				if(i == 0){
					a[i][j + 1] = z[i][j + 1] = false;
					v.push_back({i , j + 1});
				} else {
					if(!a[i - 1][j + 1]){
						a[i][j + 1] = z[i][j + 1] = false;
						v.push_back({i , j + 1});
					}
				}
			}
		}
	}
	if(!z[i][j]) return;
	z[i][j] = false;
	v.clear();
	v.push_back({i , j});
	x = 0;
	while(x < sze(v)){
		ll i = v[x].first , j = v[x++].second;
		r[i].erase(j); c[j].erase(i);
		if(i){
			if(z[i - 1][j]){
				if(!z[i - 1][j + 1]){
					z[i - 1][j] = false;
					v.push_back({i - 1 , j});
				}
			}
		}
		if(j){
			if(z[i][j - 1]){
				if(!z[i + 1][j - 1]){
					z[i][j - 1] = false;
					v.push_back({i , j - 1});
				}
			}
		}
	}
	return;
}

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

	cin>>n>>m;
	for(ll i = 0 ; i < n ; i++){
		for(ll j = 0 ; j < m ; j++){
			a[i][j] = z[i][j] = true;
			r[i].insert(j);
			c[j].insert(i);
		}
	}
	for(ll i = 0 ; i < n ; i++){
		for(ll j = 0 ; j < m ; j++){
			bool f;
			cin>>f;
			b[i][j] = f;
			if(f){
				del(i , j);
			}
		}
	}
	ll q;
	cin>>q;
	for(ll e = 0 ; e < q ; e++){
		ll i , j;
		cin>>i>>j; i--; j--;
		if(b[i][j]){
			cout<<"0\n";
			continue;
		}
		bool f = false;
		if(i){
			auto it = r[i - 1].upper_bound(j);
			f |= (it != r[i - 1].end());
		}
		if(j){
			auto it = c[j - 1].upper_bound(i);
			f |= (it != c[j - 1].end());
		}
		if(!f){
			cout<<"0\n";
			continue;
		}
		b[i][j] = true;
		del(i , j);
		cout<<"1\n";
	}
	return 0;
}

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