Областная олимпиада по информатике 2020 год, 9-11 классы


Задача A. Кролики

Ограничение по времени:
2 секунды
Ограничение по памяти:
256 мегабайт

У Айбара есть сад, который состоит из $K$ подряд идущих грядок. В саду живут $n$ кроликов. Каждый кролик находится в одной из грядок. Иногда кролики могут переходить в соседние грядки. Также, иногда Айбару нужно узнать количество кроликов, которые находятся на каком-то отрезке, чтобы их покормить. Айбару дано $q$ запросов, которые надо обработать. Они бывают следующих типов:
Формат входного файла
В первой строке входных данных даны два числа - $n$ и $K$. \\ Далее во второй строке указаны $n$ чисел - изначальное положение каждого кролика.\\ Затем в отдельной строке следует число $q$ и $q$ строк описывающих запросы. Запросы задаются в следующем формате:
Формат выходного файла
В выходные данные выведите по одному числу для каждого запроса третьего типа в отдельной строке.
Система оценки
Подзадача 1 (20 баллов) — $1 <= n, K, q <= 1000$ Подзадача 2 (20 баллов) — $1 <= n, K, q <= 5 * 10^5$, отсутствуют запросы сдвига кролика Подзадача 3 (60 баллов) — $1 <= n, K, q <= 5 * 10^5$
Пример:
Вход
3 10
4 2 8
4
G 3 7
R 2
L 3
G 3 7
Ответ
1
3
( Sanjar Bidaibek )
посмотреть в олимпиаде

Комментарий/решение:

  1
2020-01-13 16:26:21.0 #

показать/скрыть код

  -1
2020-04-24 19:31:29.0 #

показать/скрыть код

  1
2020-07-28 13:49:48.0 #

Дерево отрезков ;)

показать/скрыть код

  0
2020-11-03 11:25:12.0 #

Кому интересно это решение через Дерево Фенвика!

показать/скрыть код

  0
2021-02-23 15:41:58.0 #

показать/скрыть код

  0
2021-08-29 04:42:28.0 #

Обычное дп

показать/скрыть код

  0
2021-09-18 18:36:06.0 #

Решение на Python:

kr, gr = map(int, input().split())

sad=[]

z=0

schet=0

superschet=[]

sad=(input().split())

for i in range(len(sad)):

z=int(sad[i])

sad[i]=z

deis=input()

deis=int(deis)

for i in range(deis):

hod=input().split()

if(hod[0]=="G"):

for i in range(len(sad)):

if(sad[i]>=int(hod[1]) and sad[i]<=int(hod[2])):

schet+=1

superschet.append(schet)

schet=0

if(hod[0]=="R"):

sad[int(hod[1])-1]=sad[int(hod[1])-1]+1

if(hod[0]=="L"):

sad[int(hod[1])-1]=sad[int(hod[1])-1]-1

for i in range(len(superschet)):

print(superschet[i])