/**
* Note: The returned array must be malloced, assume caller calls free().
*/
#define For(a, b) for (a = 0 ; a < b ; a++)
int g_n;
int g_hashcnt;
int g_hashcntxy;
#define HA 200000
struct Hx {
int x;
int xout;
struct Hx *next;
};
struct Hxy {
int x;
int y;
int xout;
struct Hxy *next;
};
struct Hx * hasx[HA];
struct Hxy * g_hasxy[HA];
int flag[HA];
int a1[HA];
int a2[HA];
int a3[HA];
int a4[HA];
int* gridIllumination(int N, int** lamps, int lampsSize, int*
lampsColSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize)
{
int i;
g_n = N;
g_hashcnt = 0;
g_hashcntxy = 0;
int *out = (int *)malloc(sizeof(int) * queriesSize);
For(i, HA) {
a1[i] = 0;
a2[i] = 0;
a3[i] = 0;
a4[i] = 0
hasx[i] = NULL;
g_hasxy[i] = NULL;
flag[i] = 0;
}
For(i, lampsSize) {
Padd(lamps[i][0], lamps[i][1]);
}
For(i, queriesSize) {
out[i] = statt(queries[i][0], queries[i][1]);
Prm(queries[i][0], queries[i][1]);
}
*returnSize = queriesSize;
return out;
}
void Prm(int x, int y)
{
_Prm(x, y);
if (x - 1 >= 0) {
_Prm(x - 1, y);
if (y - 1 >= 0) _Prm(x - 1, y - 1);
if (y + 1 < g_n) _Prm(x - 1, y + 1);
}
if (x + 1 < g_n) {
_Prm(x + 1, y);
if (y - 1 >= 0) _Prm(x + 1, y - 1);
if (y + 1 < g_n) _Prm(x + 1, y + 1);
}
if (y - 1 >= 0) _Prm(x, y - 1);
if (y + 1 < g_n) _Prm(x, y + 1);
}
void Padd(int x, int y)
{
flag[hashxy(x, y)]++;
a1[hashx(x)]++;
a2[hashx(y)]++;
a3[hashx(x + y)]++;
a4[hashx(x + g_n - 1 - y)]++;
}
void _Prm(int x, int y)
{
if(flag[hashxy(x, y)] > 0) {
flag[hashxy(x, y)]--;
a1[hashx(x)]--;
a2[hashx(y)]--;
a3[hashx(x + y)]--;
a4[hashx(x + g_n - 1 - y)]--;
}
}
int statt(int x, int y)
{
if (a1[hashx(x)] > 0 || a2[hashx(y)] > 0 || a3[hashx(x + y)]
> 0 || a4[hashx(x + g_n - 1 - y)] > 0) {return 1;}
return 0;
}
int hashx(int x)
{
int temp = x % HA;
struct Hx **ptr = &hasx[temp];
next:
if (*ptr != NULL) {
if ((*ptr)->x == x)
return (*ptr)->xout;
ptr = &((*ptr)->next);
goto next;
} else {
(*ptr) = (struct Hx *)malloc(sizeof(struct Hx));
(*ptr)->x = x;
(*ptr)->xout = g_hashcnt++;
(*ptr)->next = NULL;
return (*ptr)->xout;
}
}
int hashxy(int x, int y)
{
int temp = (x + y) % HA;
struct Hxy **ptr = &g_hasxy[temp];
next:
if ((*ptr) != NULL) {
if ((*ptr)->x == x && (*ptr)->y == y)
return (*ptr)->xout;
ptr = &((*ptr)->next);
goto next;
} else {
(*ptr) = (struct Hxy *)malloc(sizeof(struct Hxy));
(*ptr)->x = x;(*ptr)->y = y;
(*ptr)->xout = g_hashcntxy;
(*ptr)->next = NULL;
return g_hashcntxy++;
}
}
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
#define For(a, b) for (a = 0 ; a < b ; a++)
int g_n;
int g_hashcnt;
int g_hashcntxy;
#define HA 200000
struct Hx {
int x;
int xout;
struct Hx *next;
};
struct Hxy {
int x;
int y;
int xout;
struct Hxy *next;
};
struct Hx * hasx[HA];
struct Hxy * g_hasxy[HA];
int flag[HA];
int a1[HA];
int a2[HA];
int a3[HA];
int a4[HA];
int* gridIllumination(int N, int** lamps, int lampsSize, int* lampsColSize,
int** queries, int queriesSize, int* queriesColSize, int* returnSize)
{
int i;
g_n = N;
g_hashcnt = 0;
g_hashcntxy = 0;
int *out = (int *)malloc(sizeof(int) * queriesSize);
For(i, HA) {
a1[i] = 0;
a2[i] = 0;
a3[i] = 0;
a4[i] = 0
hasx[i] = NULL;
g_hasxy[i] = NULL;
flag[i] = 0;
}
For(i, lampsSize) {
Padd(lamps[i][0], lamps[i][1]);
}
For(i, queriesSize) {
out[i] = statt(queries[i][0], queries[i][1]);
Prm(queries[i][0], queries[i][1]);
}
*returnSize = queriesSize;
return out;
}
void Prm(int x, int y)
{
_Prm(x, y);
if (x - 1 >= 0) {
_Prm(x - 1, y);
if (y - 1 >= 0) _Prm(x - 1, y - 1);
if (y + 1 < g_n) _Prm(x - 1, y + 1);
}
if (x + 1 < g_n) {
_Prm(x + 1, y);
if (y - 1 >= 0) _Prm(x + 1, y - 1);
if (y + 1 < g_n) _Prm(x + 1, y + 1);
}
if (y - 1 >= 0) _Prm(x, y - 1);
if (y + 1 < g_n) _Prm(x, y + 1);
}
void Padd(int x, int y)
{
flag[hashxy(x, y)]++;
a1[hashx(x)]++;
a2[hashx(y)]++;
a3[hashx(x + y)]++;
a4[hashx(x + g_n - 1 - y)]++;
}
void _Prm(int x, int y)
{
if(flag[hashxy(x, y)] > 0) {
flag[hashxy(x, y)]--;
a1[hashx(x)]--;
a2[hashx(y)]--;
a3[hashx(x + y)]--;
a4[hashx(x + g_n - 1 - y)]--;
}
}
int statt(int x, int y)
{
if (a1[hashx(x)] > 0 || a2[hashx(y)] > 0 || a3[hashx(x + y)] > 0
|| a4[hashx(x + g_n - 1 - y)] > 0) {return 1;}
return 0;
}
int hashx(int x)
{
int temp = x % HA;
struct Hx **ptr = &hasx[temp];
next:
if (*ptr != NULL) {
if ((*ptr)->x == x)
return (*ptr)->xout;
ptr = &((*ptr)->next);
goto next;
} else {
(*ptr) = (struct Hx *)malloc(sizeof(struct Hx));
(*ptr)->x = x;
(*ptr)->xout = g_hashcnt++;
(*ptr)->next = NULL;
return (*ptr)->xout;
}
}
int hashxy(int x, int y)
{
int temp = (x + y) % HA;
struct Hxy **ptr = &g_hasxy[temp];
next:
if ((*ptr) != NULL) {
if ((*ptr)->x == x && (*ptr)->y == y)
return (*ptr)->xout;
ptr = &((*ptr)->next);
goto next;
} else {
(*ptr) = (struct Hxy *)malloc(sizeof(struct Hxy));
(*ptr)->x = x;(*ptr)->y = y;
(*ptr)->xout = g_hashcntxy;
(*ptr)->next = NULL;
return g_hashcntxy++;
}
}