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

#	User	Rating
1	tourist	3690
2	jiangly	3647
3	Benq	3581
4	orzdevinwang	3570
5	Geothermal	3569
5	cnnfls_csy	3569
7	Radewoosh	3509
8	ecnerwala	3486
9	jqdai0815	3474
10	gyh20	3447

#	User	Contrib.
1	maomao90	174
2	awoo	165
3	adamant	161
4	TheScrasse	160
5	nor	158
6	maroonrk	156
7	-is-this-fft-	152
8	orz	146
9	SecondThread	145
9	pajenegod	145

Не хотел создавать данный пост — надеялся, что кто-то другой сделает, но нет :) На этой неделе проходят областные олимпиады в Беларуси. Все как обычно, два тура по 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