fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> orderedset;
  7. #define MO2 ios_base::sync_with_stdio(false);cin.tie(NULL);
  8. #define endl '\n'
  9. #define int long long
  10. #define elif else if
  11. #define sz(x) long(x.size())
  12. #define all(vec) vec.begin(), vec.end()
  13. const int mod = 1e9 + 7;
  14. const int dx[] = {0, -1, 0, 1, 1, -1, 1, -1};
  15. const int dy[] = {-1, 0, 1, 0, 1, 1, -1, -1};
  16.  
  17. int n, m;
  18. void dope() {}
  19.  
  20. void solve() {
  21.     cin >> n >> m;
  22.     vector<pair<int,int>> vec(n);
  23.     vector<int> partial_sum(2e6),Q(m);
  24.     map<int, int> mp;
  25.     set<int> st;
  26.     for (auto&it:vec) {
  27.         cin >> it.first >> it.second;
  28.         it.first += 1e9;
  29.         it.second += 1e9;
  30.         st.insert(it.first);
  31.         st.insert(it.second);
  32.     }
  33.  
  34.     for (auto&it:Q) {
  35.         cin >> it;
  36.         it += 1e9;
  37.         st.insert(it);
  38.     }
  39.  
  40.     int counter = 1;
  41.     for (auto&it:st) mp[it] = counter++;
  42.  
  43.     for (auto&it:vec) {
  44.         partial_sum[mp[it.first]]++;
  45.         partial_sum[mp[it.second] + 1]--;
  46.     }
  47.  
  48.     for (int i = 1; i < sz(partial_sum); i++)
  49.         partial_sum[i] += partial_sum[i - 1];
  50.  
  51.     for (auto&it:Q)
  52.         cout << partial_sum[mp[it]] << ' ';
  53. }
  54. signed main() {
  55.     MO2
  56. #if ONLINE_JUDGE || CPH
  57. #else
  58.     freopen("Input.txt", "r", stdin);
  59.     freopen("Output.txt", "w", stdout);
  60. #endif
  61.     int nop = 1; // cin >> nop;
  62.     while (nop--)
  63.     {
  64.         solve();
  65.         if (nop)
  66.             cout << endl;
  67.     }
  68.     return 0;
  69. }
Success #stdin #stdout 0.01s 18652KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/AbRKHJ
language:
C++ (gcc 8.3)
created:
6 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!