제출 #784563

#제출 시각아이디문제언어결과실행 시간메모리
784563hanifchdnFurniture (JOI20_furniture)C++14
0 / 100
2 ms1108 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define ld long double #define fi first #define se second const int dx[] = {0, 1}; const int dy[] = {1, 0}; int n, m; bool a[1005][1005], check[1005][1005], vis[1005][1005]; set<int> s1[1005], s2[1005]; void dfs(int x, int y) { vis[x][y] = 1; if (a[x][y]) return; for (int i = 0; i < 2; i++) { int tx = x + dx[i], ty = y + dy[i]; if (tx > n or ty > m) continue; if (!vis[tx][ty]) dfs(tx, ty); check[x][y] |= check[tx][ty]; } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) cin >> a[i][j]; } vis[n][m] = 1, check[n][m] = 1; dfs(1, 1); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (check[i][j] and check[i][j - 1]) s1[j].insert(i); if (check[i][j] and check[i - 1][j]) s2[i].insert(j); } } int q; cin >> q; while (q--) { int x, y; cin >> x >> y; if (!check[x][y]) cout << 1 << "\n"; else { auto it1 = s1[y].upper_bound(x), it2 = s2[x].upper_bound(y); if (it1 == s1[y].end() and it2 == s2[x].end()) { cout << 0 << "\n"; continue; } cout << 1 << "\n"; check[x][y] = 0, s1[y].erase(x), s1[y + 1].erase(x), s2[x].erase(y), s2[x + 1].erase(y); for (int i = x + 1; i <= n; i++) { if (!check[i][y] or check[i][y - 1]) break; check[i][y] = 0; s2[i + 1].erase(y), s1[y].erase(i + 1); } for (int j = y + 1; j <= m; j++) { if (!check[x][j] or check[x - 1][j]) break; check[x][j] = 0; s1[j + 1].erase(x), s2[x].erase(j + 1); } for (int i = x - 1; i >= 1; i--) { if (!check[i][y] or check[i][y + 1]) break; check[i][y] = 0; s2[i].erase(y), s1[y].erase(i); } for (int j = y - 1; j >= 1; j--) { if (!check[x][j] or check[x + 1][j]) break; check[x][j] = 0; s1[j].erase(x), s2[x].erase(j); } } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...