fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define N 30005
  5. vector<int> v[N];
  6. typedef pair<pair<int, int>,pair<int,int>> pi;
  7. vector<pi> pr;
  8. int tree[4*N]={0};
  9.  
  10. void update(int node,int st,int end,int x)
  11. {
  12.     if(st==end)
  13.     {
  14.         tree[node]=1;
  15.         return;
  16.     }
  17.     int m=(st+end)/2;
  18.     if(st<=x && x<=m)
  19.         update(2*node,st,m,x);
  20.     else
  21.         update(2*node+1,m+1,end,x);
  22.     tree[node]=tree[2*node]+tree[2*node+1];
  23. }
  24.  
  25. int query(int node,int st,int end,int l,int r)
  26. {
  27.     if(st>r || end<l)
  28.         return 0;
  29.     if(st>=l && end<=r)
  30.         return tree[node];
  31.  
  32.     int m=(st+end)/2;
  33.     int p1=query(2*node,st,m,l,r);
  34.     int p2=query(2*node+1,m+1,end,l,r);
  35.     return p1+p2;
  36. }
  37.  
  38. bool comp(pi a,pi b)
  39. {
  40.     return a.first.first<b.first.first;
  41. }
  42.  
  43. int main()
  44. {
  45.     ios_base::sync_with_stdio(false);
  46.     cin.tie(NULL);
  47.  
  48.     int n;
  49.     cin>>n;
  50.  
  51.     vector<int> arr,a;
  52.     for(int i=0;i<n;i++)
  53.     {
  54.         int x;
  55.         cin>>x;
  56.         arr.push_back(x);
  57.     }
  58.  
  59.     set<int> s;
  60.     for(int i=0;i<n;i++)
  61.         s.insert(arr[i]);
  62.  
  63.     for(auto it=s.begin();it!=s.end();it++)
  64.     {
  65.         a.push_back(*it);
  66.     }
  67.  
  68.     for(int i=0;i<n;i++)
  69.     {
  70.         int ind=lower_bound(a.begin(),a.end(),arr[i])-a.begin();
  71.         v[ind].push_back(i+1);
  72.     }
  73.  
  74.     int q;
  75.     cin>>q;
  76.  
  77.     for(int c=0;c<q;c++)
  78.     {
  79.         int i,j,k;
  80.         cin>>i>>j>>k;
  81.  
  82.         pr.push_back(make_pair(make_pair(k,c),make_pair(i,j)));
  83.     }
  84.     sort(pr.begin(),pr.end(),comp);
  85.  
  86.     int ans[q];
  87.     int mx=-1;
  88.     for(int i=0;i<q;i++)
  89.     {
  90.         int l=pr[i].second.first;
  91.         int r=pr[i].second.second;
  92.         int k=lower_bound(a.begin(),a.end(),pr[i].first.first)-a.begin();
  93.         int ind=pr[i].first.second;
  94.         if(a[k]>pr[i].first.first)
  95.             k--;
  96.  
  97.         while(mx<=k)
  98.         {
  99.             if(mx>=0)
  100.             {
  101.                 for(auto num:v[mx])
  102.                 {
  103.                     update(1,1,n,num);
  104.                 }
  105.             }
  106.             mx++;
  107.         }
  108.         ans[ind]=r-l+1-query(1,1,n,l,r);
  109.     }
  110.  
  111.     for(int i=0;i<q;i++)
  112.         cout<<ans[i]<<endl;
  113. }
Success #stdin #stdout 0s 4484KB
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/g2MGR6
problem KQUERY, based on SPOJ submission 26021292 (CPP14), 2020-05-22 14:23:45
language:
C++14 (gcc 8.3)
created:
3 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!