oj.uz

Submission #779814

# Submission time Handle Problem Language Result Execution time Memory
779814 2023-07-11T23:07:58 Z raysh07 Furniture (JOI20_furniture) C++17
100 / 100
 206 ms 13012 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

int n, m; 
const int N = 1005;
bool a[N][N], ok[N][N];
int cnt[2 * N];

void upd(int x, int y){
	if (!ok[x][y]) return;

	cnt[x + y]--;
	ok[x][y] = false;

	if (!ok[x - 1][y + 1]) upd(x - 1, y), upd(x, y + 1);
	if (!ok[x + 1][y - 1]) upd(x, y - 1), upd(x + 1, y);
}

void Solve()
{
	cin >> n >> m;

	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			cnt[i + j]++;
			ok[i][j] = true;
		}
	}

	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			int x; cin >> x;

			if (x) upd(i, j);
		}
	}

	int q; cin >> q;

	while(q--){
		int x, y; cin >> x >> y;

		if (!ok[x][y]) cout << 1 << "\n";
		else if (cnt[x + y] == 1) cout << 0 << "\n";
		else {
			cout << 1 << "\n";
			upd(x, y);
		}
	}
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;

  //  cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 496 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 4 ms 476 KB Output is correct
9 Correct 3 ms 468 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 496 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 4 ms 476 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 7 ms 736 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 95 ms 5972 KB Output is correct
13 Correct 38 ms 3128 KB Output is correct
14 Correct 177 ms 10776 KB Output is correct
15 Correct 191 ms 11084 KB Output is correct
16 Correct 193 ms 12008 KB Output is correct
17 Correct 202 ms 12596 KB Output is correct
18 Correct 200 ms 12144 KB Output is correct
19 Correct 206 ms 12952 KB Output is correct
20 Correct 204 ms 12972 KB Output is correct
21 Correct 202 ms 13012 KB Output is correct