Областная олимпиада по информатике 2020 год, 9-11 классы
Задача A. Қояндар
Айбарда K бөлімнен тұратын бақша бар. Бақшада n қояндар тұрады. Әрбір қоян бақшаның бір бөлімінде орналасқан. Кейде қояндар көршілес бөлімдерге өтуі мүмкін. Сондай-ақ, кейде Айбар оларды тамақтандыру үшін кейбір бөлімдердегі қояндардың санын білу керек. Айбарға q сұраныстар берілген. Олар келесі түрде болады:
- x-шi нөмірдегі қоян (1<=x<=n) бір бөлімге солға немесе оңға көшті. Бұл жағдайда қоян бақшадан тыс шықпайтынына кепілдік беріледі
- l-ден r-ге дейінгі (1<=l<=r<=K) бөлімдердегі қояндардың санын табу керек.
- L x - x-ші қоян сол жақта орналасқан бөлімге көшті
- R x - x-ші қоян оң жақта орналасқан бөлімге көшті
- G lr - l-ден бастап r-ге дейінгі аралықтағы қояндардың санын санап, шығару.
- $1 <= n, K, q <= 1000.20$ баллға бағаланады.
- $1 <= n, K, q <= 5 * 10^5.Қояндардыңкөшусұрауларыжоқ.20$ баллға бағаланады.
- $1 <= n, K, q <= 5 * 10^5.60$ баллға бағаланады.
3 10 4 2 8 4 G 3 7 R 2 L 3 G 3 7Ответ
1 3( Sanjar Bidaibek )
Комментарий/решение:
Кому интересно это решение через Дерево Фенвика!
Решение на 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])
#python
n, k = map(int, input().split())
a = list(map(int, input().split()))
g = int(input())
b = [0]
l = []
for i in range(n):
b.append(a[i])
for i in range(g):
s = input().split()
w = 0
if 'G' in s:
x = int(s[1])
y = int(s[2])
for j in b:
if x <= j <= y:
w += 1
l.append(w)
if 'R' in s:
x = int(s[1])
b[x] = b[x] + 1
if 'L' in s:
x = int(s[1])
b[x] = b[x] - 1
print(*l)
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.