fork download
copy 
  1. /*  Template:  By Jugal :) */
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. typedef long long int ll;
  5. typedef vector <int> vi;
  6. typedef vector <vi> vii;
  7. typedef pair<int,int> pii;
  8. typedef int ft;
  9. #define get getchar_unlocked 
  10. #define put putchar_unlocked 
  11. #define pb push_back 
  12. #define mp make_pair 
  13. #define ff first 
  14. #define ss second 
  15. #define sz size() 
  16. #define ln length() 
  17. #define rep(i,n) for(int i=0;i<n;i++) 
  18. #define ref(i,a,n) for(int i=a;i<=n;i++) 
  19. #define reb(i,n,a) for(int i=n;i>=a;i--) 
  20. #define all(a) a.begin(),a.end() 
  21. #define gi(n) scanf("%d",&n) 
  22. #define gii(n) scanf("%lld",&n) 
  23. #define gc(c) scanf(" %c",&c) 
  24. #define pi(n) printf("%d",n) 
  25. #define pii(n) printf("%lld",n) 
  26. #define pc(c) printf("%c",c) 
  27. #define ps printf(" ") 
  28. #define pn printf("\n") 
  29. void gl(char *str) { char c; int i=0; if((c=get())!='\n') str[i++]=c; while((c=get())!='\n') str[i++]=c;str[i]='\0'; }
  30. void pl(char *str) { rep(i,strlen(str)) put(str[i]); }
  31. void gfi(ft &x) {
  32. 	register ft c = get(); x = 0; ft sn=1;
  33.         for(;(c<48 || c>57);c = get()) if(c=='-') sn=-1;
  34.         for(;c>47 && c<58;c = get()) {x = (x<<1) + (x<<3) + c - 48;}
  35.         x*=sn;
  36. }
  37. struct node {
  38. 	int x,y,i;
  39. }q[311111];
  40.  
  41. typedef struct node nod;
  42. int a[311111],cnt[1111111],answer=0,ans[311111],BLOCK=555;
  43.  
  44. bool cmp(node x, node y) {
  45. 	if(x.x/BLOCK != y.x/BLOCK) {
  46. 		return x.x/BLOCK < y.x/BLOCK;
  47. 	}
  48. 	return x.y < y.y;
  49. }
  50.  
  51. /*int inline cmp(const void *xx,const void *yy) {
  52. 	nod *x = (nod *) xx;
  53. 	nod *y = (nod *) yy;
  54. 	if(x->x!=y->x) return (x->x>y->x)?1:-1;
  55. 	return (x->y>y->y)?1:(x->y<y->y)?-1:0;
  56. }
  57. */
  58. void add(int ind) {
  59. 	cnt[a[ind]]++;
  60. 	if(cnt[a[ind]]==1) answer++;
  61. }
  62.  
  63. void rem(int ind) {
  64. 	cnt[a[ind]]--;
  65. 	if(cnt[a[ind]]==0) answer--;
  66. }
  67.  
  68. int main() {
  69. 	int n,query;
  70. 	gfi(n);
  71. 	rep(i,n) gfi(a[i]);
  72. 	gfi(query);
  73. 	rep(i,query) {
  74. 		gfi(q[i].x);gfi(q[i].y);
  75. 		q[i].x--;q[i].y--;
  76. 		q[i].i=i;
  77. 	}
  78. 	sort(q,q+query,cmp);
  79. 	int ll=0,rr=0;
  80. 	rep(i,query) {
  81. 		int l=q[i].x,r=q[i].y;
  82. 		while(ll<l) rem(ll++);
  83. 		while(ll>l) add(--ll);
  84. 		while(rr<=r) add(rr++);
  85. 		while(rr>r+1) rem(--rr);
  86. 		ans[q[i].i]=answer;
  87. 	}
  88. 	rep(i,query) pi(ans[i]),pn;
  89. 	return 0;
  90. }
  91.  
Time limit exceeded #stdin #stdout 5s 13560KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/xnDfoX
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!