fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define deb(x) cout<<#x<<" "<<x<"\n"
  5.  
  6. vector<ll> seg[400005];     ///2D vector: to store elements at each node level
  7. vector<ll> a(30002);
  8.  
  9. void builtTree(int low, int high, int node)
  10. {
  11.     if(low==high)
  12.     {
  13.         seg[node].emplace_back(a[low]);
  14.         return;
  15.     }
  16.     int mid=(low+high)/2;
  17.     builtTree(low,mid,2*node+1);
  18.     builtTree(mid+1,high,2*node+2);
  19.     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]));
  20. }
  21.  
  22. ll query(int qlow, int qhigh, int low, int high, ll node, ll k)
  23. {
  24.     if(qlow>high || low>qhigh)      /// no overlapping
  25.         return 0;
  26.  
  27.     if(low>=qlow && high<=qhigh)
  28.     {
  29.         return seg[node].size()-(upper_bound(seg[node].begin(),seg[node].end(),k)-seg[node].begin());
  30.     }
  31.  
  32.     int mid=(low+high)/2;
  33.     ll left=query(qlow, qhigh, low, mid, 2*node+1, k);
  34.     ll right=query(qlow, qhigh, mid+1, high, 2*node+2, k);
  35.     return left+right;
  36. }
  37.  
  38. main()
  39. {
  40.     ios_base::sync_with_stdio(false);
  41.     cin.tie(NULL);
  42.     cout.tie(NULL);
  43.  
  44.     int n,q,i;
  45.     cin>>n;
  46.     for(i=0;i<n;i++)
  47.         cin>>a[i];
  48.  
  49.     builtTree(0,n-1,0);
  50.     cin>>q;
  51.     int l,r;
  52.     ll k;
  53.     while(q--)
  54.     {
  55.         cin>>l>>r>>k;
  56.         if(l>r || l>n || r>n)
  57.             cout<<"0\n";
  58.         else if(l==r)
  59.         {
  60.             a[l-1]>k?cout<<"1\n":cout<<"0\n";
  61.         }
  62.         else
  63.         cout<<query(l-1,r-1,0,n-1,0,k)<<"\n";
  64.     }
  65.  
  66. }
Runtime error #stdin #stdout 0s 12928KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/nz5Wjj
problem KQUERY, based on SPOJ submission 24276062 (C++ 4.3.2), 2019-08-21 16:08:10
language:
C++ 4.3.2 (gcc-4.3.2)
created:
4 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!