fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define ii pair<int, int>
  4. #define st first
  5. #define nd second
  6. #define endl "\n"
  7. #define all(v) v.begin(), v.end()
  8.  
  9. using namespace std;
  10.  
  11. const int MAXN = 1e6 + 5;
  12.  
  13. int n, k;
  14. vector<int> s[MAXN], t[MAXN];
  15.  
  16. signed main()
  17. {
  18.     ios_base::sync_with_stdio(false);
  19.     cin.tie(0);
  20.  
  21.     cin >> n >> k;
  22.  
  23.     multiset<ii> s1;
  24.     priority_queue<ii> s2;
  25.  
  26.     vector<ii> g;
  27.     for (int i = 1; i <= n; i++)
  28.     {
  29.         int x, y;
  30.         cin >> x >> y;
  31.         s[y].push_back(x);
  32.         t[x].push_back(y);
  33.     }
  34.  
  35.  
  36.     for (int x = 1e6; x >= 1; x--){
  37.         for (auto y : t[x]){
  38.             if (s1.size() < k) s1.insert({x, y});
  39.             else s2.push({x, y});
  40.         }
  41.  
  42.     }
  43.  
  44.  
  45.     ll ans = 0;
  46.  
  47.     for (int y = 1; y <= 1e6; y++){
  48.         while (s1.size() < k && s2.size()){
  49.             if (s2.top().nd >= y) s1.insert(s2.top());
  50.             s2.pop();
  51.         }
  52.         while (s2.size() && s2.top().nd < y) s2.pop();
  53.         if (s1.size() < k) break;
  54.         if (s2.size())
  55.             ans += s1.begin()->st - s2.top().st;
  56.         else ans += s1.begin()->st;
  57.         for (auto x : s[y]){
  58.             if (s1.size() && s1.find({x, y}) != s1.end()) s1.erase({x, y});
  59.         }
  60.     }
  61.     cout << ans << endl;
  62.  
  63. }
  64.  
Success #stdin #stdout 0.03s 50472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/aiw7Yz
language:
C++14 (gcc 8.3)
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!