fork download
  1. #include<stdio.h>
  2. #include<algorithm>
  3. #define bl 174
  4. typedef long long ll;
  5. struct node{
  6. ll l,r,p;
  7. }q[200006];
  8. ll ar[30005],cnt[1000006],answer=0,ans[2000006];
  9. bool sorting(node a,node b)
  10. {
  11. if((a.l/bl)!=(b.l)/bl)
  12. {
  13. return((a.l/bl)<(b.l/bl));
  14. }
  15. return (a.r<b.r);
  16.  
  17. }
  18. void remove(ll p)
  19. {
  20. cnt[ar[p]]--;
  21. if(cnt[ar[p]]==0)
  22. {
  23. answer--;
  24. }
  25. }
  26. void add(ll p)
  27. {
  28. cnt[ar[p]]++;
  29. if(cnt[ar[p]]==1)
  30. answer++;
  31. }
  32. int main()
  33. {
  34. using namespace std;
  35. ll i,m,n;
  36. scanf("%lld",&n);
  37. for(i=0;i<n;i++)
  38. scanf("%lld",&ar[i]);
  39. scanf("%lld",&m);
  40. for(i=0;i<m;i++)
  41. {
  42. scanf("%lld%lld",&q[i].l,&q[i].r);
  43. q[i].l--;
  44. q[i].r--;
  45. q[i].p=i;
  46. }
  47. sort(q,q+m,sorting);
  48. ll cl=0,cr=0,x,y;
  49. for(i=0;i<m;i++)
  50. {
  51. x=q[i].l;
  52. y=q[i].r;
  53. while(cl<x)
  54. {
  55. remove(cl);
  56. cl++;
  57. }
  58. while(cl>x)
  59. {
  60. add(cl-1);
  61. cl--;
  62. }
  63. while(cr<=y)
  64. {
  65. add(cr);
  66. cr++;
  67. }
  68. while(cr>y+1)
  69. {
  70. remove(cr-1);
  71. cr--;
  72. }
  73. ans[q[i].p]=answer;
  74. }
  75. for(i=0;i<m;i++)
  76. printf("%lld\n",ans[i]);
  77. return 0;
  78. }
Time limit exceeded #stdin #stdout 5s 31824KB
stdin
Standard input is empty
stdout
Standard output is empty