fork(1) download
copy 
  1. #include<stdio.h>
  2. long long int n;
  3. long long int t[1000009] = {0}; // Segement Tree
  4. long long int arr[70009] = {0}; // Original Input
  5. long long int output[700009] = {0}; 
  6. struct node{
  7. 	long long int org; // Original Position
  8. 	long long int kval;
  9. 	long long int l;
  10. 	long long int r;
  11. 	long long int qry; // For Query it's 1 else 0
  12. };
  13. struct node p[700009]; // To store both Queries and Array Elements
  14. int compare(const void *x,const void *y){
  15. 	struct node *k1 = (struct node *)x;
  16. 	struct node *k2 = (struct node *)y;
  17.     if(k1->kval > k2->kval)
  18.     	return 1;
  19.     else if(k1->kval < k2->kval)
  20.     	return -1;
  21.     else{
  22.     	if(k1->qry == 1){
  23.     		return 1;
  24. 		}
  25. 		else if(k2->qry == 1){
  26. 			return -1;
  27. 		}
  28. 	}
  29. }
  30. //Iterative Segment Tree
  31. long long int sum(long long int l,long long int r){  // Find Sum in range [l,r)
  32. 	long long int res = 0;
  33. 	for(l = n+l,r = n+r; l < r ; l = l>>1,r = r>>1){
  34. 		if(l&1) { res += t[l++];}
  35. 		if(r&1) { res += t[--r];} 
  36. 	}
  37. 	return res;
  38. }
  39. void update(long long int pos,long long int nval){ 
  40. 	pos = pos + n;
  41. 	for(t[pos] = nval; pos > 0 ;pos = pos>>1 ){
  42. 		t[pos >> 1] = t[pos] + t[pos^1];
  43. 	}
  44. }
  45. int main(){
  46. 	long long int i,m=0,l,r;
  47. 	scanf("%lld",&n);
  48. 	for(i = 0 ; i < n ; i++){
  49. 		scanf("%lld",&arr[i]);
  50. 		p[i].org  = i;
  51. 		p[i].qry  = 0; // Not a Query
  52. 		p[i].kval = arr[i]; 
  53. 		p[i].l    = -1;
  54. 		p[i].r    = -1; 
  55. 	}
  56. 	scanf("%lld",&m);//Queries
  57. 	long long int j = 0;
  58. 	//We have i=n here
  59. 	for(j = 0 ; j < m ; j++,i++){
  60. 		long long int val;
  61. 		scanf("%lld %lld %lld",&l,&r,&val);
  62. 		p[i].org  = j;
  63. 		p[i].kval = val;
  64. 		p[i].qry  = 1; 
  65. 		p[i].l    = l-1;
  66. 		p[i].r    = r;// r-1 for recursive
  67. 	}
  68. 	long long int b = n+m;//total elements + queries
  69. 	qsort(p,b,sizeof(p[0]),compare); 
  70. 	for(i = n+m-1 ; i >=0 ; i--){
  71. 		if(p[i].qry == 0){  
  72. 			update(p[i].org,1);// We update the Segment Tree to have value 1  
  73. 		}
  74. 		else if(p[i].qry == 1){
  75. 			long long int res   = sum(p[i].l,p[i].r);
  76. 			output[p[i].org] = res;  //Query's Original Position
  77. 		}
  78. 	}
  79.  
  80. 	for(i = 0 ; i < m ; i++){
  81. 		printf("%lld\n",output[i]);
  82. 	}
  83. 	return 0;
  84. }
  85.  
Success #stdin #stdout 0s 43344KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/GDJB5Q
language:
C (gcc 8.3)
created:
7 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!