Editor

Different Visitors in a Stretch

#642 · Data structures · Expert · Fast enough · 250 XP · about 50 min

A museum records the membership number of every visitor at the door, in order: visits[0] is the first visit on record. Members come back often, so a number can appear many times. The managers ask many questions of the form "how many different members came between visit first and visit last?", with both of those visits included.

Write distinct_visitors(visits, queries) that returns a list with the answer to each (first, last) pair in queries, in order.

Examples

distinct_visitors([4, 2, 4, 7, 2, 2], [(0, 5), (1, 3), (4, 5), (2, 2)])
# returns [3, 3, 1, 1]

Visits 1 to 3 are members 2, 4 and 7: 3 different members. Visits 4 and 5 are both member 2.

Constraints

  • 1 <= len(visits) <= 60,000
  • 0 <= len(queries) <= 60,000
  • Membership numbers are whole numbers from 1 to 1,000,000,000.
  • 0 <= first <= last < len(visits)

Time limit

Each test must finish within 10 seconds, and the hidden tests ask 60,000 questions about 60,000 visits.

Fastest solvers

Leaderboard

First solves only, ranked by stars and then time.