fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int solution(const vector<int> &a, const vector<int> &b, int m) {
  5.     const int n = a.size();
  6.     set<int> s, fixed;
  7.     set<pair<int, int>> smaller, largea, largeb;
  8.     for (int i = 0; i < n; ++i) {
  9.         if (a[i] < b[i]) {
  10.             smaller.insert({a[i], i});
  11.         } else if (a[i] == b[i]) {
  12.             fixed.insert(a[i]);
  13.         } else {
  14.             largea.insert({a[i], i});
  15.             largeb.insert({b[i], i});
  16.         }
  17.         s.insert(a[i]);
  18.         s.insert(b[i]);
  19.     }
  20.     int r = INT_MAX;
  21.     set<pair<int, int>> topa, topb;
  22.     for (int x : s) {
  23.         // we want all values >= x
  24.         while (!smaller.empty() && smaller.begin()->first < x) {
  25.             if (m-- == 0) return r;
  26.             fixed.insert(b[smaller.begin()->second]);
  27.             smaller.erase(smaller.begin());
  28.         }
  29.         if (!fixed.empty() && *fixed.begin() < x) return r;
  30.         if (!largea.empty() && largea.begin()->first < x) return r;
  31.         if (!topa.empty() && topa.begin()->first < x) return r;
  32.         while (!largeb.empty() && largeb.begin()->first < x) {
  33.             const int ind = largeb.begin()->second;
  34.             fixed.insert(a[ind]);
  35.             largea.erase({a[ind], ind});
  36.             largeb.erase(largeb.begin());
  37.         }
  38.         while (!topb.empty() && topb.begin()->first < x) {
  39.             const int ind = topb.begin()->second;
  40.             fixed.insert(a[ind]);
  41.             topa.erase({a[ind], ind}); 
  42.             topb.erase(topb.begin());
  43.         }
  44.         while (topa.size() > m) {
  45.             largea.insert(*topa.begin());
  46.             const int ind = topa.begin()->second;
  47.             largeb.insert({b[ind], ind});
  48.             topa.erase(topa.begin());
  49.             topb.erase({b[ind], ind});
  50.         }
  51.         while (topa.size() < m && !largea.empty()) {
  52.             topa.insert(*largea.rbegin());
  53.             const int ind = largea.rbegin()->second;
  54.             topb.insert({b[ind], ind});
  55.             largea.erase({a[ind], ind});
  56.             largeb.erase({b[ind], ind});
  57.         }
  58.         int m = INT_MIN;
  59.         if (!smaller.empty()) {
  60.             m = max(m, smaller.rbegin()->first);
  61.         }
  62.         if (!fixed.empty()) {
  63.             m = max(m, *fixed.rbegin());
  64.         }
  65.         if (!largea.empty()) {
  66.             m = max(m, largea.rbegin()->first);
  67.         }
  68.         if (!topb.empty()) {
  69.             m = max(m, topb.rbegin()->first);
  70.         }
  71.         r = min(r, m - x);
  72.     }
  73.  
  74.     return r;
  75. }
  76.  
  77. int main() {
  78.     cout << solution({1, 2, 17, 16, 9}, {3, 4, 5, 6, 11}, 2) << endl;
  79.     cout << solution({1, 100}, {99999, 100000}, 2) << endl;
  80.     cout << solution({1, 100}, {99999, 100000}, 1) << endl;
  81.     return 0;
  82. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
8
1
99
https://ideone.com/C06nJM
language:
C++ (gcc 8.3)
created:
175 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!