Submission #534301

#	Time	Username	Problem	Language	Result	Execution time	Memory
534301		pavement	Furniture (JOI20_furniture)	C++17	100 / 100	327 ms	35544 KiB

furniture

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

int N, M, Q, R[1005][1005], cnt[2005], T[2][1005][1005], dr[] = {-1, 0, 0, 1}, dc[] = {0, -1, 1, 0};
bool C;

void rem(int r, int c) {
	if (R[r][c]) return;
	R[r][c] = 1;
	cnt[r + c]--;
	for (int k = 0; k < 4; k++) {
		if (1 <= r + dr[k] && r + dr[k] <= N && 1 <= c + dc[k] && c + dc[k] <= M) {
			T[k / 2][r + dr[k]][c + dc[k]]--;
			if (T[k / 2][r + dr[k]][c + dc[k]] == 0) rem(r + dr[k], c + dc[k]);
		}
	}
}

main() {
	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++) {
			cnt[i + j]++;
			T[0][i][j] = 2 - (i == N) - (j == M);
			T[1][i][j] = 2 - (i == 1) - (j == 1);
		}
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++) {
			cin >> C;
			if (C == 1) rem(i, j);
		}
	cin >> Q;
	for (int r, c; Q--; ) {
		cin >> r >> c;
		if (R[r][c]) cout << "1\n";
		else if (cnt[r + c] == 1) cout << "0\n";
		else {
			cout << "1\n";
			rem(r, c);
		}
	}
}

Compilation message (stderr)

furniture.cpp:44:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   44 | main() {
      | ^~~~

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