oj.uz

Submission #623112

# Submission time Handle Problem Language Result Execution time Memory
623112 2022-08-05T08:15:05 Z S2speed Furniture (JOI20_furniture) C++17
100 / 100
 1091 ms 113536 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 980 KB Output is correct
2 Correct 3 ms 852 KB Output is correct
3 Correct 5 ms 1236 KB Output is correct
4 Correct 7 ms 1492 KB Output is correct
5 Correct 7 ms 1364 KB Output is correct
6 Correct 9 ms 1516 KB Output is correct
7 Correct 6 ms 1492 KB Output is correct
8 Correct 6 ms 1620 KB Output is correct
9 Correct 6 ms 1460 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 980 KB Output is correct
2 Correct 3 ms 852 KB Output is correct
3 Correct 5 ms 1236 KB Output is correct
4 Correct 7 ms 1492 KB Output is correct
5 Correct 7 ms 1364 KB Output is correct
6 Correct 9 ms 1516 KB Output is correct
7 Correct 6 ms 1492 KB Output is correct
8 Correct 6 ms 1620 KB Output is correct
9 Correct 6 ms 1460 KB Output is correct
10 Correct 36 ms 5844 KB Output is correct
11 Correct 6 ms 1492 KB Output is correct
12 Correct 1091 ms 95040 KB Output is correct
13 Correct 530 ms 84792 KB Output is correct
14 Correct 1054 ms 94564 KB Output is correct
15 Correct 1037 ms 90260 KB Output is correct
16 Correct 603 ms 97536 KB Output is correct
17 Correct 788 ms 103364 KB Output is correct
18 Correct 1020 ms 100800 KB Output is correct
19 Correct 734 ms 108440 KB Output is correct
20 Correct 773 ms 113536 KB Output is correct
21 Correct 739 ms 109808 KB Output is correct