Hi! I encounter difficulties in finding a solution to this problem: having a matrix filled with 0 and 1, size N x N with N <= 1000, output the number of squares with the border filled with 1 (we are not interested in what's inside the square). We consider valid even the squares of size 1x1. For this example, the answer is 27. Can anybody help me? (sorry for the example, I don't know how to show the lines one above the others) 0000000 0111100 0101111 0100101 0111111 0000011 0000011
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
12:09:35
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
12:09:35
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.11.2024 05:25:26 (j3).
Десктопная версия, переключиться на мобильную.
При поддержке
I think a 2D BIT should be enough to solve this task.
Can you tell me more detalis how?
The best I have is O(n3) solution with
constant. I think it can pass if the time limit is two seconds (maybe even one second with powerful judge).
The time limit is 0.15 seconds
Solve each diagonal separately. You need to use 2D-segment tree or 2D-BIT for O(n*n*log(n)*log(n)) complexity or persistent segment tree for O(n*n*log(n)) complexity.