#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
#define F first
#define S second
ll min(ll x, ll y){
return ((x < y) ? x : y);
}
ll max(ll x, ll y){
return ((x > y) ? x : y);
}
class Grid{
private:
ll w,h;
vvi c;
vii upper_path; // minimize y value
vii left_path; // minimize x value
bool check (ll x, ll y){
return (h > x && x >= 0 && w > y && y >= 0);
}
void modify_path(ll x, ll y, vii& path, ll dx, ll dy){
/*
cout << "reached: " << x << " " << y << " " << dx << " " << dy << endl;
if (c[x+dx][y+dy] == 1){
add(x+dx,y+dy);
}else{
path[x+y] = ii(x+dx,y+dy);
}
c[x][y] = 1;
if (check(x-dx,y))
add(x-dx,y);
if (check(x,y-dy))
add(x,y-dy);
*/
while (c[path[x+y].F][path[x+y].S] == 1){
path[x+y].F += dx;
path[x+y].S += dy;
}
ll bdx = max(dx,0), sdx = min(dx,0);
ll bdy = max(dy,0), sdy = min(dy,0);
for (ll i = x+y-1; i >= 0; i--){
ll diff = abs(path[i+1].F-path[i].F) + abs(path[i+1].F-path[i].F);
if (diff == 1) break;
ii cd = path[i+1];
cd.F -= bdx; cd.S -= bdy;
if (check(cd.F,cd.S) && c[cd.F][cd.S] == 0){
path[i] = cd;
}else{
cd.F += bdx; cd.S += bdy;
cd.F += sdx; cd.S += sdy;
path[i] = cd;
}
}
for (ll i = x+y+1; w+h-2 >= i; i++){
ll diff = abs(path[i-1].F-path[i].F) + abs(path[i-1].F-path[i].F);
if (diff == 1) break;
ii cd = path[i-1];
cd.F -= sdx; cd.S -= sdy;
if (check(cd.F,cd.S) && c[cd.F][cd.S] == 0){
path[i] = cd;
}else{
cd.F += bdx; cd.S += bdy;
cd.F += sdx; cd.S += sdy;
path[i] = cd;
}
}
}
public:
Grid(ll _h, ll _w){
w = _w; h = _h;
c.assign(h,vi(w,0));
upper_path.resize(w+h-1);
left_path.resize(w+h-1);
for (ll i = 0; w+h-1 > i; i++){
upper_path[i] = ii(max(0,i-w+1),min(i,w-1));
left_path[i] = ii(min(i,h-1),max(0,i-h+1));
}
}
ll add (ll x, ll y){
//cout << "called: " << x << " " << y << endl;
if (left_path[x+y] == ii(x,y) && upper_path[x+y] == ii(x,y)) return 0;
c[x][y] = 1;
if (upper_path[x+y] == ii(x,y)) modify_path(x,y,upper_path, 1, -1);
if (left_path[x+y] == ii(x,y)) modify_path(x,y,left_path, -1, 1);
return 1;
}
void print(){
cout << "upper_path: \n";
for (auto i: upper_path){
cout << "(" << i.F << " , " << i.S << ") -> ";
}
cout << endl;
cout << "left_path:\n";
for (auto i: left_path){
cout << "(" << i.F << " , " << i.S << ") -> ";
}
cout << "c:\n";
for (auto i: c){
for (auto j: i) cout << j << " ";
cout << endl;
}
cout << endl;
}
};
int main(){
ll h,w;
cin >> h >> w;
Grid grid(h,w);
//grid.print();
for (ll i = 0; h > i; i++){
for (ll j = 0; w > j; j++){
ll x; cin >> x;
//cout << "added: " << i << " " << j << endl;
if (x) grid.add(i,j);
}
}
ll q; cin >> q;
//grid.print();
while (q--){
ll x, y; cin >> x >> y;
x--; y--;
cout << grid.add(x,y) << '\n';
//grid.print();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
332 KB |
Output is correct |
| 2 |
Runtime error |
4 ms |
460 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
332 KB |
Output is correct |
| 2 |
Runtime error |
4 ms |
460 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
