#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 2000 + 7;
int n;
int m;
int a[N][N];
int down[N][N];
void full()
{
down[n + 1][m] = down[n][m + 1] = 1;
for (int i = n; i >= 1; i--)
{
for (int j = m; j >= 1; j--)
{
if (a[i][j] == 0)
{
down[i][j] = (down[i + 1][j] > 0) + (down[i][j + 1] > 0);
}
else
{
down[i][j] = 0;
}
}
}
}
void upd(int r, int c)
{
for (int i = r; i >= 1; i--)
{
for (int j = c; j >= 1; j--)
{
if (a[i][j] == 0)
{
down[i][j] = (down[i + 1][j] > 0) + (down[i][j + 1] > 0);
}
else
{
down[i][j] = 0;
}
}
}
}
int 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++)
{
cin >> a[i][j];
}
}
full();
int q;
cin >> q;
for (int i = 1; i <= q; i++)
{
int r, c;
cin >> r >> c;
a[r][c] = 1;
upd(r, c);
if (down[1][1] == 0)
{
a[r][c] = 0;
upd(r, c);
cout << "0\n";
}
else
{
cout << "1\n";
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1024 KB |
Output is correct |
2 |
Correct |
20 ms |
1152 KB |
Output is correct |
3 |
Correct |
39 ms |
1272 KB |
Output is correct |
4 |
Correct |
78 ms |
1152 KB |
Output is correct |
5 |
Correct |
88 ms |
1280 KB |
Output is correct |
6 |
Correct |
105 ms |
1292 KB |
Output is correct |
7 |
Correct |
82 ms |
1424 KB |
Output is correct |
8 |
Correct |
78 ms |
1280 KB |
Output is correct |
9 |
Correct |
67 ms |
1280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1024 KB |
Output is correct |
2 |
Correct |
20 ms |
1152 KB |
Output is correct |
3 |
Correct |
39 ms |
1272 KB |
Output is correct |
4 |
Correct |
78 ms |
1152 KB |
Output is correct |
5 |
Correct |
88 ms |
1280 KB |
Output is correct |
6 |
Correct |
105 ms |
1292 KB |
Output is correct |
7 |
Correct |
82 ms |
1424 KB |
Output is correct |
8 |
Correct |
78 ms |
1280 KB |
Output is correct |
9 |
Correct |
67 ms |
1280 KB |
Output is correct |
10 |
Correct |
1492 ms |
1400 KB |
Output is correct |
11 |
Correct |
62 ms |
896 KB |
Output is correct |
12 |
Execution timed out |
5094 ms |
17912 KB |
Time limit exceeded |
13 |
Halted |
0 ms |
0 KB |
- |