fork(3) download
copy 
  1. #include<bits/stdc++.h>
  2. #include<algorithm>
  3. using namespace std;
  4. #define mp make_pair
  5. int arr[30005],query[1000005],memo[200005];
  6. class node
  7. {
  8. 	public:vector< pair< int,pair<int,int> > >link;
  9. };
  10.  
  11. #define vppi pair< int,pair<int,int> >
  12. node dp[200];
  13.  
  14. #define gc getchar_unlocked
  15.  
  16. inline void scanint(int &x)
  17. {
  18.     register int c = gc();
  19.     x = 0;
  20.     for(;(c<48 || c>57);c = gc());
  21.     for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
  22. }
  23.  
  24. inline void add(int i,int *answer)
  25. {
  26. 	query[arr[i]]++;
  27. 	if(query[arr[i]]==1) (*answer)++;
  28. }
  29.  
  30. inline void remove(int i,int *answer)
  31. {
  32.     query[arr[i]]--;
  33.    	if(query[arr[i]]==0) (*answer)--;
  34.  
  35. }
  36.  
  37. inline bool compare3( vppi a,vppi b)
  38. {
  39. 	return a.second.second<b.second.second;
  40. }
  41.  
  42. int main()
  43. {
  44. 	int t,n,q,i,j,k,sq,a,b,m;
  45. 	scanint(n);
  46. 	for(i=0;i<n;i++) scanint(arr[i]);
  47. 	sq=ceil( (double)sqrt(n) );
  48. 	scanint(m);
  49. 	t=m;
  50. 	j=0;
  51. 	while(t--)
  52. 	{ 
  53.  
  54. 	   	scanint(a);
  55. 	   	scanint(b);
  56. 		i=(a-1)/sq;
  57. 	    dp[i].link.push_back(mp(j,mp(a-1,b-1)));
  58. 		j++;
  59.  
  60. 	}
  61.  
  62. 	for(i=0;i<sq;i++)
  63. 	{
  64. 		j=dp[i].link.size();
  65. 		if(j!=0) sort(dp[i].link.begin(),dp[i].link.end(),compare3);
  66. 	}
  67.  
  68. 	memset(query,0,sizeof(query));
  69.  
  70. 	int ans=0;
  71.  
  72.  
  73. 	int currentL=0,currentR=0,L,R;
  74. 	for(i=0;i<=sq;i++)
  75. 	{
  76. 		j=dp[i].link.size();
  77. 		for(k=0;k<j;k++)
  78. 	    {
  79.  
  80. 	    	L=dp[i].link[k].second.first;
  81. 	    	R=dp[i].link[k].second.second;
  82. 	        while( currentL <L) 
  83. 		    {
  84. 		        remove(currentL,&ans);
  85.                 currentL++;
  86.             }
  87.  
  88. 	        while( currentL >L)
  89.             {
  90.                 add(currentL-1,&ans);
  91.                 currentL--;
  92.             }
  93.             while( currentR <=R)
  94.             {
  95.                add(currentR,&ans);
  96.                currentR++;
  97.             }
  98.             while( currentR >R+1)
  99.             {
  100.                 remove(currentR-1,&ans);
  101.                 currentR--;	
  102. 		    }
  103.  
  104. 		    memo[dp[i].link[k].first]=ans;
  105.  
  106. 	    }
  107.  
  108. 	}
  109.  
  110. 	for(i=0;i<m;i++) 
  111. 	{
  112. 		printf("%d\n",memo[i]);
  113. 	}
  114. }
Success #stdin #stdout 0s 8224KB
comments (?)
stdin
copy 
5
1 1 2 1 3
3
1 5
2 4
3 5
stdout
copy 
3
2
3
https://ideone.com/vwX6mY
language:
C++14 (gcc 8.3)
created:
8 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!