Белорусская областная олимпиада 2019

#	User	Rating
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

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Не хотел создавать данный пост — надеялся, что кто-то другой сделает, но нет :) На этой неделе проходят областные олимпиады в Беларуси. Все как обычно, два тура по 4 задачи, 5 часов на их решение. Здесь предлагаю обсудить задачки, решения и так далее.

Первый тур

Задача 1. Олимп-Сити

Решение

Решение на C++.

Задача 2. Дружелюбные соседи

Решение

Решение на C++.

Задача 3. Поворот плиток

Решение

Решение на C++.

Задача 4. Садовник

Решение

Научимся отвечать на запросы без модификаций массива. Для начала положим, что z_i не убывают. Будем хранить новый массив t. Для i-го запроса, он будет выглядеть так:
t_i = 0, если a_i > z_i,
t_i = 1, если a_i ≤ z_i.
Как переходит от i-го массива к i + 1 понятно — нужно в нужных местах добавить 1. Чтобы отвечать на запрос от l до r, нам необходимо посчитать сумму на отрезке в массиве t. Чтобы делать это быстро, будем хранить t как дерево отрезков.

Теперь избавимся от ограничения на z_i. Для этого сделаем наше дерево отрезков персистентным. Большему z_i должна соответствовать большая версия, поэтому чтобы построить такое дерево отрезков, отсортируем исходный массив a_i и занесем в персистентное дерево отрезков. Для всех возможных значений z_i запомним максимальный номер версии, запрос к которой будет соответсвовать запросу l_i, r_i, z_i. Будем хранить номер в массиве v. Отвечать на запросы мы научились.

Теперь посмотрим, что происходит, когда мы делаем операцию инкремента чисел равных x. Если до инкремента запросу l, r, x соответсвовал запрос в дереве отрезков с версией v[x], то после инкремента ответ можно получить в v[x - 1]. Для чисел не равных x не поменялось ничего. Поэтому, чтобы выполнить операцию инкремента, нам необходимо сделать v[x] = v[x - 1].

Сложность по времени: $\text{[math]}$ , по памяти: $\text{[math]}$

Решение на C++.

Rev.	By	When	Δ	Comment
ru9	wilcot	2019-01-12 11:07:21	60
ru8	wilcot	2019-01-12 11:06:30	156
ru7	wilcot	2019-01-12 10:55:34	56
ru6	wilcot	2019-01-12 00:33:01	1413
ru5	wilcot	2019-01-10 22:12:07	1008
ru4	wilcot	2019-01-10 21:41:58	432
ru3	wilcot	2019-01-09 22:37:53	2	Мелкая правка: ' как обычны, два тура' -> ' как обычно, два тура'
ru2	wilcot	2019-01-09 22:35:40	2
ru1	wilcot	2019-01-09 22:35:16	3082	Первая редакция (опубликовано)

Первый тур

Задача 1. Олимп-Сити

Задача 2. Дружелюбные соседи

Задача 3. Поворот плиток

Задача 4. Садовник

History