fork download
copy 
  1. #include<stdio.h>
  2. #include<algorithm>
  3. #define bl 174
  4. typedef long long ll;
  5. #define gc getchar_unlocked
  6. #define pc(x) putchar_unlocked(x);
  7.    inline void print(ll n)
  8.     {
  9.         ll N = n, rev, count = 0;
  10.         rev = N;
  11.         if (N == 0) { pc('0'); pc('\n'); return ;}
  12.         while ((rev % 10) == 0) { count++; rev /= 10;} //obtain the count of the number of 0s
  13.         rev = 0;
  14.         while (N != 0) { rev = (rev<<3) + (rev<<1) + N % 10; N /= 10;}  //store reverse of N in rev
  15.         while (rev != 0) { pc(rev % 10 + '0'); rev /= 10;}
  16.         while (count--) pc('0');
  17.     }
  18. ll read_int() {
  19.   char c = gc();
  20.   while(c<'0' || c>'9') c = gc();
  21.   ll ret = 0;
  22.   while(c>='0' && c<='9') {
  23.     ret = 10 * ret + c - 48;
  24.     c = gc();
  25.   }
  26.   return ret;
  27. }
  28. struct node{
  29. 	ll l,r,p;
  30. }q[200006];
  31. ll ar[30005],cnt[1000006],answer=0,ans[2000006];
  32. bool sorting(node a,node b)
  33. {
  34. 	if((a.l/bl)!=(b.l)/bl)
  35. 	{
  36. 		return((a.l/bl)<(b.l/bl));
  37. 	}
  38. 	return (a.r<b.r);
  39.  
  40. }
  41. void remove(ll p)
  42. {
  43. 	cnt[ar[p]]--;
  44. 	if(cnt[ar[p]]==0)
  45. 	{
  46. 		answer--;
  47. 	}
  48. }
  49. void add(ll p)
  50. {
  51. 	cnt[ar[p]]++;
  52. 	if(cnt[ar[p]]==1)
  53. 	answer++;
  54. }
  55. int main()
  56. {
  57. 	using namespace std;
  58. 	ll i,m,n;
  59. 	n=read_int();
  60. 	for(i=0;i<n;i++)
  61. 	ar[i]=read_int();
  62. 	m=read_int();
  63. 	for(i=0;i<m;i++)
  64. 	{
  65. 		q[i].l=read_int();
  66. 		q[i].r=read_int();
  67. 		q[i].l--;
  68. 		q[i].r--;
  69. 		q[i].p=i;
  70. 	}
  71. 	sort(q,q+m,sorting);
  72. 	ll cl=0,cr=0,x,y;
  73. 	for(i=0;i<m;i++)
  74. 	{
  75. 		x=q[i].l;
  76. 		y=q[i].r;
  77. 		while(cl<x)
  78. 		{
  79. 			remove(cl);
  80. 			cl++;
  81. 		}
  82. 		while(cl>x)
  83. 		{
  84. 			add(cl-1);
  85. 			cl--;
  86. 		}
  87. 		while(cr<=y)
  88. 		{
  89. 			add(cr);
  90. 			cr++;
  91. 		}
  92. 		while(cr>y+1)
  93. 		{
  94. 			remove(cr-1);
  95. 			cr--;
  96. 		}
  97. 		ans[q[i].p]=answer;
  98. 	}
  99. 	for(i=0;i<m;i++)
  100. 	{
  101. 	print(ans[i]);
  102. 	printf("\n");
  103. }
  104. return 0;
  105. }
Time limit exceeded #stdin #stdout 5s 31776KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/MqzGnu
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

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!