fork download
  1. import sys
  2. import os,io
  3. input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
  4.  
  5. n = int(input())
  6. arr = list(map(int, input().split()))
  7. sqr = int(n**0.5)
  8. m = int(input())
  9. query = []
  10. for i in range(m):
  11. a, b = map(int, input().split())
  12. query.append((a-1, b-1, i))
  13. query.sort(key=lambda x: (x[0]//sqr, x[1]))
  14.  
  15. l, r = 0, -1
  16. count = 0
  17. d = [0] * 1000000
  18. result = [0] * m
  19. for a, b, i in query:
  20. while l > a:
  21. l -= 1
  22. if d[arr[l]] == 0:
  23. count += 1
  24. d[arr[l]] += 1
  25.  
  26. while r < b:
  27. r += 1
  28. if d[arr[r]] == 0:
  29. count += 1
  30. d[arr[r]] += 1
  31.  
  32. while l < a:
  33. d[arr[l]] -= 1
  34. if d[arr[l]] == 0:
  35. count -= 1
  36. l += 1
  37.  
  38. while r > b:
  39. d[arr[r]] -= 1
  40. if d[arr[r]] == 0:
  41. count -= 1
  42. r -= 1
  43.  
  44. result[i] = str(count)
  45.  
  46. print("\n".join(result))
Runtime error #stdin #stdout #stderr 0.16s 33292KB
stdin
3
1000000 1000000 1000000
3
1 2
2 3
1 3
stdout
Standard output is empty
stderr
Traceback (most recent call last):
  File "./prog.py", line 28, in <module>
IndexError: list index out of range