fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7.  
  8.  inline void write(int x){
  9.  
  10.          register char buffor[35];
  11.          register int i=0;
  12.          do{
  13.                buffor[i++]=(x%10)+'0';
  14.                x/=10;
  15.             } while(x);
  16.            i--;
  17.             while(i>=0) putchar_unlocked(buffor[i--]);
  18.             putchar_unlocked('\n');
  19.        }
  20.  
  21. inline void fastinput(int &x){
  22.  
  23.         x=0;
  24.         register char c=getchar();
  25.         for(;c<'0' || c>'9';c=getchar());
  26.          for(;c>='0' && c<='9';c=getchar())
  27.           x=(x<<3)+(x<<1)+(c-'0');
  28.       }
  29.  
  30. const int N=30005;
  31. int arr[N];
  32. vector<int> seg[4*N];
  33.  
  34. void build(int low,int high,int node)
  35. {
  36.     if(low>high)
  37.     return;
  38.     if(low == high)
  39.     {
  40.         seg[node].push_back(arr[low]);
  41.         return;
  42.     }
  43.     int mid=low+high>>1;
  44.     build(low,mid,2*node+1);
  45.     build(mid+1,high,2*node+2);
  46.     merge(seg[2*node+1].begin(),seg[2*node+1].end(),seg[2*node+2].begin(),seg[2*node+2].end(),back_inserter(seg[node]));
  47. }
  48.  
  49. int query(int low,int high,int lq,int hq,int k,int node)
  50. {
  51.     if(low>high || low>hq || high<lq)
  52.     return 0;
  53.     if(lq<=low && high<=hq)
  54.     {
  55.         // to count all the elements greater then k in the seg[node] vector.
  56.         return seg[node].size()-(upper_bound(seg[node].begin(),seg[node].end(),k)-seg[node].begin());
  57.     }
  58.     int left=0,right=0;
  59.     int mid=low+high>>1;
  60.     left = query(low,mid,lq,hq,k,2*node+1);
  61.     right = query(mid+1,high,lq,hq,k,2*node+2);
  62.     return left+right;
  63. }
  64. int main(){
  65.     int n;
  66.     fastinput(n);
  67.     register int i;
  68.     for(i = 0; i < n; i++)
  69.     {
  70.         fastinput(arr[i]);
  71.     }
  72.     int q;
  73.     fastinput(q);
  74.     int x,y,k;
  75.     build(0,n-1,0);
  76.     while(q--)
  77.     {
  78.         fastinput(x);
  79.         fastinput(y);
  80.         fastinput(k);
  81.         write(query(0,n-1,x-1,y-1,k,0));
  82.     }
  83.     return 0;
  84. }
Success #stdin #stdout 0s 18168KB
comments (?)
stdin
copy 
5
5 1 2 3 4
3
2 4 1
4 4 4
1 5 2
stdout
copy 
2
0
3
https://ideone.com/YQIaM1
language:
C++ (gcc 8.3)
created:
6 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!