Miawinator: Pagină nouă: = Cerința = Se dă un vector cu `n` elemente. Să se determine numărul de secvențe care au medianul valorilor egal cu `k`. = Date de intrare = Fișierul de intrare `input.txt` contine pe prima linie un număr `N` reprezentând numărul de elemente din vector și un număr `k` cu semnificația din enunț. Pe a doua linie se află `N` elemente , elementele vectorului. = Date de ieșire = Fișierul de ieșire...

2024-01-05T02:44:51Z

Pagină nouă: = Cerința = Se dă un vector cu <code>n</code> elemente. Să se determine numărul de secvențe care au medianul valorilor egal cu <code>k</code>. = Date de intrare = Fișierul de intrare <code>input.txt</code> contine pe prima linie un număr <code>N</code> reprezentând numărul de elemente din vector și un număr <code>k</code> cu semnificația din enunț. Pe a doua linie se află <code>N</code> elemente , elementele vectorului. = Date de ieșire = Fișierul de ieșire...

New page

= Cerința =
Se dă un vector cu <code>n</code> elemente. Să se determine numărul de secvențe care au medianul valorilor egal cu <code>k</code>.

= Date de intrare =
Fișierul de intrare <code>input.txt</code> contine pe prima linie un număr <code>N</code> reprezentând numărul de elemente din vector și un număr <code>k</code> cu semnificația din enunț. Pe a doua linie se află <code>N</code> elemente , elementele vectorului.

= Date de ieșire =
Fișierul de ieșire <code>output.txt</code> contine pe prima linie răspunsul.

= Restricții și precizări =

* <code>N ≤ 100.000</code>, <code>K ≤ 1.000.000.000</code>

== Exemplul 1 ==
input.txt:

2 2

1 2

output.txt:

1

== Exemplul 2 ==
input.txt:

3 5

5 1 5

output.txt:

3

== Exemplul 3 ==
input.txt:

3 99999999999

5 1 5

Output:

Invalid input constraints.

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
MOD = 666013
Nmax = 100001
Add = 100000

def verify_constraints(n, k):
if not (1 <= n <= 100000 and 1 <= k <= 1000000000):
print("Invalid input constraints.")
exit()

def Update(pos, val):
global aib
i = pos
while i < Nmax * 2:
aib[i] += val
i += i & -i

def Query(pos):
global aib
i = pos
sum_ = 0
while i > 0:
sum_ += aib[i]
i -= i & -i
return sum_

def Fx(k):
global n, V, aib

aib = [0] * (Nmax * 2)

S = [0] * (n + 1)

for i in range(1, n + 1):
if V[i] > k:
S[i] = -1
else:
S[i] = 1

for i in range(2, n + 1):
S[i] += S[i - 1]

for i in range(1, n + 1):
Update(S[i] + Add, 1)

s = 0

for i in range(1, n + 1):
s += Query(S[i] + Add - 1)

if S[i] < 0:
s += 1

Update(S[i] + Add, -1)

return s

with open("input.txt", "r") as fin, open("output.txt", "w") as fout:
n, k = map(int, fin.readline().split())
verify_constraints(n,k)
V = [0] + list(map(int, fin.readline().split()))

sk = Fx(k)
skk = Fx(k - 1)

fout.write(str(abs(sk - skk)))

</syntaxhighlight>

3831 - Medians - Revision history