fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <queue>
  4.  
  5. using namespace std;
  6.  
  7. constexpr int MAX = 1000007;
  8. int n, k_range, range_check;
  9.  
  10. struct rangeof
  11. {
  12.     int p, k;
  13.     int nr;
  14.  
  15.     void read(int i)
  16.     {
  17.         cin >> p >> k;
  18.         nr = i;
  19.     }
  20. };
  21.  
  22. rangeof tabp[MAX]; 
  23.  
  24. int maximum = 0;
  25.  
  26. bool sort_by_first(const rangeof & z1, const rangeof & z2)
  27. {
  28.     if (z1.p < z2.p)
  29.         return true;
  30.     else if (z1.p == z2.p && z1.k > z2.k)
  31.         return true;
  32.  
  33.     return false;
  34. }
  35.  
  36. struct range {
  37.     int p, k;
  38. };
  39.  
  40. bool visited[MAX];
  41.  
  42. int range(const rangeof & z)
  43. {
  44.     return z.k - z.p;
  45. }
  46.  
  47. bool reached_k = false;
  48.  
  49. void do_odd1(rangeof z1, int i, int k)
  50. {
  51.     rangeof pom;
  52.  
  53.     while (++i <= n && ++k <= k_range)
  54.     {
  55.         if (z1.k <= tabp[i].p)
  56.             return;
  57.  
  58.         pom.p = max(z1.p, tabp[i].p);
  59.         pom.k = min(z1.k, tabp[i].k);
  60.  
  61.         int dl = range(pom);
  62.  
  63.         if (reached_k && dl <= maximum)
  64.         {
  65.             --k;
  66.             continue;
  67.         }
  68.  
  69.         if (k == k_range) {
  70.             if (!reached_k)
  71.                 reached_k = true;
  72.             if (dl > maximum)
  73.                 maximum = dl;
  74.             --k;
  75.             continue;
  76.         }
  77.  
  78.         do_odd1(pom, i, k);
  79.         --k;
  80.     }
  81. }
  82.  
  83. void do_main()
  84. {
  85.     for (int i = 1; i <= range_check; ++i)
  86.     {
  87.         if (!visited[i])
  88.         {
  89.             do_odd1(tabp[i], i, 1);
  90.         }
  91.     }
  92. }
  93.  
  94. int main()
  95. {
  96.     std::ios_base::sync_with_stdio(0);
  97.  
  98.     cin >> n >> k_range;
  99.  
  100.     range_check = n - k_range - 1;
  101.  
  102.     for (int i = 1; i <= n; ++i) {
  103.         tabp[i].read(i);
  104.     }
  105.  
  106.     std::sort(tabp + 1, tabp + n + 1, sort_by_first);
  107.  
  108.     do_main();
  109.  
  110.     cout << maximum << endl;
  111. }
Success #stdin #stdout 0s 28760KB
comments (?)
stdin
copy 
6 3
3 8
4 12
2 6
1 10
5 9
11 12
stdout
copy 
4
https://ideone.com/sYCVeL
language:
C++14 (gcc 8.3)
created:
6 years 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!