Skip to main content
Učilnica FRI 24/25
  • Home
  • More
Close
Toggle search input
English ‎(en)‎
English ‎(en)‎ Slovenščina ‎(sl)‎ Македонски ‎(mk)‎ Русский ‎(ru)‎ 한국어 ‎(ko)‎
You are currently using guest access
Log in
Učilnica FRI 24/25
Home
Expand all Collapse all
  1. aps1uni
  2. Drevesne strukture
  3. Vreča

Vreča

Completion requirements
Due: Sunday, 1 December 2024, 11:59 PM

Implementirajte vrečo (bag/multiset), ki bo hranila cela števila in omogočala dodajanje elementov, odstranjevanje elementov in poizvedbe o trenutnem številu elementov v vreči, ki imajo vrednost z danega intervala $[a_i, b_i]$, torej vključno z obema mejama. Če je neko število večkrat dodano v vrečo, mora vreča hraniti več enakih števil. Ko pa želimo neko število odstaniti iz vreče, v primeru več enakih elementov odstranimo zgolj enega. Če števila ni v vreči, odstranjevanje ne spremeni vsebine vreče.

Omejitve podatkov:

  • $1 \leq N \leq 10^6$
  • $1 \leq x_i \leq 10^6$ (nabor možnih vrednosti je dokaj majhen)
  • $|s_i| \leq 10^6$

Vhodni in izhodni podatki:

V prvi vrstici je najprej podano število operacij $N$. V naslednjih $N$ vrsticah so pari števil $s_i, x_i$, kjer $s_i<0$ pomeni, da število $x_i$ dodamo v vrečo, $s_i=0$ pomeni, da število $x_i$ odstranimo iz vreče in $s_i>0$, da naredimo poizvedbo na intervalu $[a_i, b_i]$, kjer je $a_i=\min(s_i, x_i)$ in $b_i=\max(s_i, x_i)$.

Na izhodu izpišemo število, ki ga dobimo, če seštejemo rezultate poizvedb.

Primer vhoda:

12
-1 2
-1 12
-3 4
-1 2
1 3
0 2
1 2
4 2
0 53
0 12
900 9
1 100

Pravilen izhod:

7

Odgovori na poizvedbe so po vrsti 2, 1, 2, 0, in 2.

You are currently using guest access (Log in)
Get the mobile app
Powered by Moodle
Obvestilo o avtorskih pravicah