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.  
  5. using namespace __gnu_pbds;
  6. #define ll long long
  7. #define nl '\n'
  8. #define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
  9. using namespace std;
  10. //order_of_key (k) : Number of items strictly smaller than k .
  11. //find_by_order(k) : K th element in a set (counting from zero)
  12.  
  13. int main()
  14. {
  15.     ios::sync_with_stdio(false);
  16.     cin.tie(NULL);
  17.     cout.tie(NULL);
  18.  
  19.     int t;
  20.     cin >> t;
  21.  
  22.     while (t--) {
  23.         int n, h;
  24.         cin >> n >> h;
  25.  
  26.         vector<ll> v(n, n);
  27.         vector<ll> pr(n + 1, 0);
  28.         for (int i = 0; i < n; i++) {
  29.             int x, y;
  30.             cin >> x >> y;
  31.             x--;
  32.             pr[x]++;
  33.             pr[y]--;
  34.  
  35.         }
  36.         for (int i = 1; i < n; i++)
  37.             pr[i] += pr[i - 1];
  38.  
  39.         for (int i = 0; i < n; i++) {
  40.             v[i] -= pr[i];
  41.         }
  42.  
  43.         sort(v.begin(), v.end());
  44.  
  45.         ll sum = 0;
  46.         for (int i = 0; i < h; i++)
  47.             sum += v[i];
  48.  
  49.         cout << sum << nl;
  50.     }
  51.  
  52.     return 0;
  53. }
  54.  
Success #stdin #stdout 0s 5272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/X0lBUR
language:
C++14 (gcc 8.3)
created:
10 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!