fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int
  4.  
  5. ll arr[100001] = {0}; // array for points
  6.  
  7. vector<ll> solve(vector<vector<ll>>& lamps,vector<ll>& points){
  8.  
  9. vector<ll>ans(points.size());
  10.  
  11. // iterating on queries
  12. for(ll i=0;i<lamps.size();i++){
  13. ll L = lamps[i][0];
  14. ll R = lamps[i][1];
  15. arr[L] += 1;
  16. arr[R+1] += -1;
  17. }
  18.  
  19. // now doing prefix sum on points array
  20. for(ll i=1;i<=100000;i++){
  21. arr[i] += arr[i-1];
  22. }
  23.  
  24. for(ll i=0;i<points.size();i++){
  25. ans[i] = arr[points[i]];
  26. }
  27. return ans;
  28. }
  29.  
  30. int main() {
  31. ll q;
  32. cin>>q;
  33. ll n;
  34. vector<vector<ll>>lamps(q,vector<ll>(2));
  35. for(ll i=0;i<q;i++){
  36. for(ll j=0;j<2;j++){
  37. cin>>lamps[i][j];
  38. }
  39. }
  40. cin>>n;
  41. vector<ll>points(n);
  42. for(ll i=0;i<n;i++){
  43. cin>>points[i];
  44. }
  45.  
  46. vector<ll>ans = solve(lamps,points);
  47.  
  48. for(int x:ans){
  49. cout<<x<<" ";
  50. }
  51. return 0;
  52. }
Success #stdin #stdout 0.01s 5280KB
stdin
3
1 7
5 11
7 9
6
7 1 5 10 9 15
stdout
3 1 2 1 2 0