oj.uz

Submission #294040

# Submission time Handle Problem Language Result Execution time Memory
294040 2020-09-08T14:38:38 Z Mlxa Furniture (JOI20_furniture) C++14
100 / 100
 397 ms 9336 KB 
#ifdef LC
#include "pch.h"
#else
#include <bits/stdc++.h>
#endif

using namespace std;
#define all(x) x.begin(), x.end()
#define x first
#define y second
#define mp make_pair
#define mt make_tuple

const int N = 1010;
int n, m, q;
bool lu[N][N];
bool rd[N][N];
bool dp[N][N];
int fen[N][N];
int pref(int x, int y) {
	int s = 0;
	for (int i = x; i >= 0; i = (i & (i + 1)) - 1) {
		for (int j = y; j >= 0; j = (j & (j + 1)) - 1) {
			s += fen[i][j];
		}
	}
	return s;
}
bool rec(int a, int b, int c, int d) {
	--a;
	--c;
	return pref(b, d) - pref(a, d) - pref(b, c) + pref(a, c) > 0;
}
void upd(int x, int y, int d) {
	for (int i = x; i < N; i |= i + 1) {
		for (int j = y; j < N; j |= j + 1) {
			fen[i][j] += d;
		}
	}
}
bool can_off(int i, int j) {
	if (!dp[i][j]) {
		return true;
	}
	return rec(1, i - 1, j + 1, m) || rec(i + 1, n, 1, j - 1);
}
void lu_dfs(int i, int j) {
	if (i < 1 || j < 1) {
		return;
	}
	if (dp[i][j] && !dp[i + 1][j] && !dp[i][j + 1]) {
		dp[i][j] = false;
		upd(i, j, -1);
		lu_dfs(i - 1, j);
		lu_dfs(i, j - 1);
	}
}
void rd_dfs(int i, int j) {
	if (i > n || j > m) {
		return;
	}
	if (dp[i][j] && !dp[i - 1][j] && !dp[i][j - 1]) {
		dp[i][j] = false;
		upd(i, j, -1);
		rd_dfs(i + 1, j);
		rd_dfs(i, j + 1);
	}
}
void print() {
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			cout << dp[i][j] << " ";
		}
		cout << "\n";
	}
}

signed main() {
#ifdef LC
	assert(freopen("input.txt", "r", stdin));
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			cin >> dp[i][j];
			dp[i][j] ^= 1;
		}
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			lu[i][j] = dp[i][j] && (lu[i - 1][j] || lu[i][j - 1]);
			lu[1][1] = true;
		}
	}
	for (int i = n; i >= 1; --i) {
		for (int j = m; j >= 1; --j) {
			rd[i][j] = dp[i][j] && (rd[i + 1][j] || rd[i][j + 1]);
			rd[n][m] = true;
			dp[i][j] = lu[i][j] && rd[i][j];
			upd(i, j, dp[i][j]);
		}
	}
	cin >> q;
	while (q--) {
		int x, y;
		cin >> x >> y;
		if (can_off(x, y)) {
			if (dp[x][y]) {
				upd(x, y, -1);
			}
			dp[x][y] = false;
			lu_dfs(x - 1, y);
			lu_dfs(x, y - 1);
			rd_dfs(x + 1, y);
			rd_dfs(x, y + 1);
			cout << "1\n";
		} else {
			cout << "0\n";
		}
	}
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 896 KB Output is correct
2 Correct 2 ms 1024 KB Output is correct
3 Correct 3 ms 1024 KB Output is correct
4 Correct 4 ms 1024 KB Output is correct
5 Correct 5 ms 1152 KB Output is correct
6 Correct 6 ms 1152 KB Output is correct
7 Correct 6 ms 1152 KB Output is correct
8 Correct 5 ms 1152 KB Output is correct
9 Correct 5 ms 1152 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 896 KB Output is correct
2 Correct 2 ms 1024 KB Output is correct
3 Correct 3 ms 1024 KB Output is correct
4 Correct 4 ms 1024 KB Output is correct
5 Correct 5 ms 1152 KB Output is correct
6 Correct 6 ms 1152 KB Output is correct
7 Correct 6 ms 1152 KB Output is correct
8 Correct 5 ms 1152 KB Output is correct
9 Correct 5 ms 1152 KB Output is correct
10 Correct 13 ms 896 KB Output is correct
11 Correct 4 ms 768 KB Output is correct
12 Correct 277 ms 7896 KB Output is correct
13 Correct 129 ms 7032 KB Output is correct
14 Correct 378 ms 8568 KB Output is correct
15 Correct 391 ms 8572 KB Output is correct
16 Correct 361 ms 8824 KB Output is correct
17 Correct 372 ms 9208 KB Output is correct
18 Correct 388 ms 8932 KB Output is correct
19 Correct 397 ms 9336 KB Output is correct
20 Correct 372 ms 9336 KB Output is correct
21 Correct 379 ms 9336 KB Output is correct