fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define endl '\n';
  3. using namespace std;
  4. typedef long long int LL;
  5.  
  6. struct query{
  7.    int l,r,k,id;
  8. }q[200005],tmp;
  9.  
  10. bool cmp(query q1, query q2){
  11. 	return q1.k>q2.k;
  12. }
  13.  
  14. int res[200005],bit[30004];
  15. pair<int,int> v[30004];
  16.  
  17. void update(int id,int val, int n){
  18.     while(id<=n){
  19.         bit[id]+=val;
  20.         id+=(id)&(-id);
  21.     }
  22. }
  23.  
  24. int query(int id){
  25.    int sum=0;
  26.    while(id>0){
  27.    	 sum+=bit[id];
  28.    	 id-=(id)&(-id);
  29.    }
  30.    return sum;
  31. }
  32.  
  33. int main()
  34. {
  35.   ios_base::sync_with_stdio(false);cin.tie(0);
  36.  
  37.   //freopen("input.in","r",stdin);
  38.  
  39.      int n;cin>>n;
  40.  
  41.      for(int i=1;i<=n;i++)
  42.       {
  43.          int x; cin>>x;
  44.          v[i-1]=make_pair(x,i);
  45.       }
  46.  
  47.      int Q;cin>>Q;for(int i=0;i<Q;i++){
  48.         cin>>tmp.l>>tmp.r>>tmp.k;
  49.         tmp.id=i;
  50.         q[i]=tmp;
  51.      } 
  52.  
  53.      sort(v,v+n);
  54.      sort(q,q+Q,cmp);
  55.  
  56.      int top=n-1;
  57.      for(int i=0;i<Q;i++)
  58.      {
  59.  
  60.         while(v[top].first>q[i].k){
  61.             update(v[top].second,1,n);
  62.         	top--;
  63.         }
  64.         int sum=query(q[i].r)-query(q[i].l-1);
  65.      	res[q[i].id]=sum;
  66.      }  
  67.  
  68.      for(int i=0;i<Q;i++)cout<<res[i]<<endl;    
  69.  
  70.   return 0;
  71. }
Success #stdin #stdout 0s 20320KB
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/t5oKHJ
problem KQUERY, based on SPOJ submission 18745494 (CPP14), 2017-02-11 17:58:23
language:
C++14 (gcc 8.3)
created:
7 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!