fork download
copy 
  1. '''
  2. Author: Kislay Sinha
  3. Link: https://w...content-available-to-author-only...j.com/problems/DQUERY/
  4. '''
  5.  
  6. from sys import stdin,stdout
  7. import math
  8.  
  9. class Query:
  10.     def __init__(self,idx,l,r):
  11.         self.idx=idx
  12.         self.L=l
  13.         self.R=r
  14.  
  15.  
  16. def add(idx):
  17.     global count
  18.     freq[nums[idx]]+=1
  19.     if freq[nums[idx]]==1:
  20.         count+=1
  21.  
  22. def remove(idx):
  23.     global count
  24.     freq[nums[idx]]-=1
  25.     if freq[nums[idx]]==0:
  26.         count-=1
  27.  
  28.  
  29. n=int(stdin.readline())
  30. nums=list(map(int,stdin.readline().split()))
  31.  
  32. q=int(stdin.readline())
  33.  
  34. queries=[]
  35.  
  36. freq=[0]*pow(10,6)
  37.  
  38. for i in range(q):
  39.     l,r=list(map(int,stdin.readline().split()))
  40.     l,r=l-1,r-1
  41.     query=Query(i,l,r)
  42.     queries.append(query)
  43.  
  44. queries.sort(key=lambda x: x.R)
  45.  
  46. ans=[0]*q
  47.  
  48. ml=0;mr=-1
  49.  
  50. count=0
  51.  
  52. for query in queries:
  53.     L=query.L
  54.     R=query.R
  55.  
  56.     while mr<R:
  57.         mr+=1
  58.         add(mr)
  59.  
  60.     while ml>L:
  61.         ml-=1
  62.         add(ml)
  63.  
  64.     while mr>R:
  65.         mr-=1
  66.         remove(mr)
  67.  
  68.     while ml<L:
  69.         remove(ml)
  70.         ml+=1
  71.  
  72.     ans[query.idx]=count
  73.  
  74. for i in ans:
  75.     stdout.write(str(i)+'\n')
Success #stdin #stdout 0.03s 16952KB
comments (?)
stdin
copy 
5
1 1 2 1 3
3
1 5
2 4
3 5
stdout
copy 
3
2
3
https://ideone.com/41MxdP
language:
Python 3 (python  3.9.5)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!