fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int main(){
  4.     int n , q;
  5.     cin >> n >> q;
  6.  
  7.     vector<int> a(n);
  8.     for(int i=0;i<n;++i)cin >> a[i];
  9.  
  10.     vector<int> red = a;
  11.     vector<vector<int>> queries;
  12.     for(int i=0;i<q;++i){
  13.         int l,r,v1,v2;
  14.         cin >> l >> r >> v1 >> v2 ;
  15.  
  16.         queries.push_back({r,v2,i,1});
  17.         queries.push_back({l,v1-1,i,-1});
  18.         red.push_back(v2);
  19.         red.push_back(v1-1);
  20.     }
  21.  
  22.     sort(begin(red), end(red));
  23.     red.erase( unique(begin(red), end(red)) , end(red));
  24.     int m = red.size() + 2;
  25.  
  26.     sort(begin(queries), end(queries));
  27.     vector<int> bit(m,0);
  28.  
  29.     auto update = [&](int index,int value)->void{
  30.         for(;index<m;index+=index&-index)bit[index]+=value;
  31.     };
  32.  
  33.     auto ask = [&](int index)->int{
  34.         int ret=0;
  35.         for(;index>0;index-=index&-index) ret += bit[index];
  36.         return ret;
  37.     };
  38.  
  39.     auto compressed_value = [&](int val)->int{
  40.         return lower_bound(begin(red), end(red), val) - begin(red) + 1;
  41.     };
  42.  
  43.     int it = 0;
  44.  
  45.     vector<int> answer(q,0);
  46.     for(auto query : queries){
  47.         const int value = compressed_value(query[1]);
  48.         for(;it<n && it<=query[0];++it) update( compressed_value(a[it]), 1);
  49.         answer[query[2]] += query[3] * ask(value);
  50.     }
  51.  
  52.     for(int i=0;i<q;++i) cout << answer[i] << "\n" ;
  53. }
Success #stdin #stdout 0.01s 5476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/J2zIQj
language:
C++14 (clang 8.0)
created:
1 year 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!