fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<int> solution(vector<vector<int>>& lamps, vector<int>& points) {
  5.     vector<int> all_coords;
  6.  
  7.     // Collect all start, end + 1, and point coordinates
  8.     for (auto& lamp : lamps) {
  9.         all_coords.push_back(lamp[0]);
  10.         all_coords.push_back(lamp[1] + 1); // exclusive end for sweep
  11.     }
  12.     for (int p : points) {
  13.         all_coords.push_back(p);
  14.     }
  15.  
  16.     // Coordinate compression
  17.     sort(all_coords.begin(), all_coords.end());
  18.     all_coords.erase(unique(all_coords.begin(), all_coords.end()), all_coords.end());
  19.  
  20.     map<int, int> coord_to_index;
  21.     for (int i = 0; i < all_coords.size(); ++i) {
  22.         coord_to_index[all_coords[i]] = i;
  23.     }
  24.  
  25.     // Build diff array
  26.     vector<int> diff(all_coords.size() + 2, 0);
  27.     for (auto& lamp : lamps) {
  28.         int start = coord_to_index[lamp[0]];
  29.         int end = coord_to_index[lamp[1] + 1];
  30.         diff[start] += 1;
  31.         diff[end] -= 1;
  32.     }
  33.  
  34.     // Prefix sum
  35.     vector<int> prefix(diff.size(), 0);
  36.     prefix[0] = diff[0];
  37.     for (int i = 1; i < diff.size(); ++i) {
  38.         prefix[i] = prefix[i - 1] + diff[i];
  39.     }
  40.  
  41.     // Answer queries
  42.     vector<int> result;
  43.     for (int p : points) {
  44.         int idx = coord_to_index[p];
  45.         result.push_back(prefix[idx]);
  46.     }
  47.  
  48.     return result;
  49. }
  50.  
  51. int main() {
  52.     vector<vector<int>> lamps = {{1, 7}, {5, 11}, {7, 9}};
  53.     vector<int> points = {7, 1, 5, 10, 9, 15};
  54.  
  55.     vector<int> ans = solution(lamps, points);
  56.  
  57.     for (int count : ans) {
  58.         cout << count << " ";
  59.     }
  60.     cout << endl;
  61.  
  62.     return 0;
  63. }
  64.  
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
10
aba
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
stdout
copy 
3 1 2 1 2 0
https://ideone.com/Qn822k
language:
C++ (gcc 8.3)
created:
5 days 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!