Problem Link . I tried to solve this problem but couldn't solve it. Try to read editorial using google translate help me nothing.

# | User | Rating |
---|---|---|

1 | tourist | 3707 |

2 | Benq | 3672 |

3 | Radewoosh | 3655 |

4 | ksun48 | 3547 |

5 | jiangly | 3492 |

6 | Miracle03 | 3480 |

7 | ecnerwala | 3400 |

8 | maroonrk | 3385 |

9 | peehs_moorhsum | 3384 |

10 | sunset | 3338 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 215 |

2 | YouKn0wWho | 190 |

2 | Um_nik | 190 |

4 | sus | 183 |

5 | awoo | 182 |

6 | Errichto | 179 |

7 | tourist | 177 |

8 | -is-this-fft- | 173 |

9 | Radewoosh | 170 |

10 | Ashishgup | 169 |

Problem Link . I tried to solve this problem but couldn't solve it. Try to read editorial using google translate help me nothing.

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/29/2021 01:32:17 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

The solution here hinges on the fact that we don't care about most of the 3x3 subrectangles.

Let's pick any uncolored cell. You can see that any 3x3 subrectangle that would contain that cell would be fully contained within the 5x5 subrectangle in which that cell is the middle. This means that if no cell in the 5x5 subrectangle where the target cell is the middle is colored, then we don't care about that point.

At most $$$9$$$ subrectangles will go through a single point, so there are at most $$$9N$$$ subrectangles we have to worry about. For each point, generate the subrectangles that contain that point (you can iterate through the position in the subrectangle that our target point is in, also be careful about edges). Also, remove duplicates in some way. This process is probably $$$O(nlogn)$$$ because of sorting or something.

Now, for each subrectangle, we will count how many colored cells are in it. We can do this by keeping each point in some ordered list (perhaps a C++

`set`

) and checking each of the 9 points in each rectangle. This is our answer.The total number of rectangles is $$$(H - 2) * (W - 2)$$$, and if we haven't looked at a rectangle, it has 0 points inside it, so you can just subtract the number of rectangles we've looked at and add that to $$$count(0)$$$.

I got bored and wanted to prove that the constant wouldn't be too bad, so here's a submission with time = 396 ms.

Thanx for the explanation, I implemented the solution but my exe time is 1144ms. Please explain why ? My solution

I would imagine constantly inserting into the set

`used`

instead of using a`vector`

and removing duplicates would perform significantly slower because`set`

is slow.Also, the use of the

`check`

function ends up looking at more points than the faster solution, because if a square would be out of bounds, the faster solution wouldn't even look at the square, but you would query the set for some of the points before deciding that it's an invalid square.