fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define faster ios_base::sync_with_stdio(false); cin.tie(NULL)
  4. #define Bit(mask , i) ((mask >> i) & 1)
  5. #define fi first
  6. #define se second
  7. #define _LOG2(nl) 31 - __builtin_clz(nl)
  8. #define c_bit(nl) __builtin_popcount(nl)
  9. #define ii pair<long long , int>
  10. #define lll pair<long long , pair<long long , long long>>
  11. #define lii pair<long long , pair<long long , int>>
  12. #define iii pair<int , pair<int , int>>
  13. #define iiii pair<pair<int , int> , pair<int , int>>
  14. #define llll pair<pair<__int128 , __int128> , pair<__int128 , __int128>>
  15. #define li pair<long long , int>
  16. #define db long double
  17. #define onBit(mask , i) (mask | (1 << i))
  18. #define offBit(mask , i) (mask & (~(1 << i)))
  19.  
  20. const long long INF = 1e16;
  21. const int N = 5e5 + 7;
  22. long long _min[21][N] , _max[21][N] , _min_b[21][N] , _min_c[21][N] , _min_d[21][N];
  23. int n;
  24.  
  25. struct gv{
  26.     long long c , s;
  27. };
  28.  
  29. gv a[N];
  30.  
  31. bool cmp(gv x , gv y){
  32.     return x.c < y.c;
  33. }
  34.  
  35. void inp(){
  36.     cin >> n;
  37.     for (int i = 1 ; i <= n ; ++i){
  38.         cin >> a[i].c >> a[i].s;
  39.     }
  40.  
  41.     sort(a + 1 , a + n + 1 , cmp);
  42. //    for (int i = 1 ; i <= n ; ++i){
  43. //        cout << a[i].c << " " << a[i].s << '\n';
  44. //    }
  45.     for (int i = 1 ; i <= n ; ++i){
  46.         _max[0][i] = a[i].s;
  47.         _min[0][i] = a[i].s;
  48.     }
  49.  
  50.     for (int j = 1 ; j <= 19 ; ++j){
  51.         for (int i = 1 ; i + (1 << j) - 1 <= n ; ++i){
  52.             _max[j][i] = max(_max[j - 1][i] , _max[j - 1][i + (1 << j - 1)]);
  53.             _min[j][i] = min(_min[j - 1][i] , _min[j - 1][i + (1 << j - 1)]);
  54.         }
  55.     }
  56. }
  57.  
  58. long long get_max(int l , int r){
  59.     if (l > r) return 0;
  60.     int k = _LOG2(r - l + 1);
  61.     return max(_max[k][l] , _max[k][r - (1 << k) + 1]);
  62. }
  63.  
  64. long long get_min(int l , int r){
  65.     if (l > r) return INF;
  66.     int k = _LOG2(r - l + 1);
  67.     return min(_min[k][l] , _min[k][r - (1 << k) + 1]);
  68. }
  69.  
  70. void ktao(){
  71.     for (int i = 1 ; i < n ; ++i){
  72.         _min_b[0][i] = a[i].c - get_min(i + 1 , n);
  73.         _min_c[0][i] = a[i].c + get_max(i + 1 , n);
  74.         _min_d[0][i] = a[i].c + get_max(i + 1 , n) - get_min(i + 1 , n);
  75.     }
  76.     _min_b[0][n] = a[n].c;
  77.     _min_c[0][n] = a[n].c;
  78.     _min_d[0][n] = a[n].c;
  79.  
  80.     for (int j = 1 ; j <= 19 ; ++j){
  81.         for (int i = 1 ; i + (1 << j) - 1 <= n ; ++i){
  82.             _min_b[j][i] = min(_min_b[j - 1][i] , _min_b[j - 1][i + (1 << j - 1)]);
  83.             _min_c[j][i] = min(_min_c[j - 1][i] , _min_c[j - 1][i + (1 << j - 1)]);
  84.             _min_d[j][i] = min(_min_d[j - 1][i] , _min_d[j - 1][i + (1 << j - 1)]);
  85.         }
  86.     }
  87. }
  88.  
  89. long long get_min_b(int l , int r){
  90.     if (l > r) return INF;
  91.     int k = _LOG2(r - l + 1);
  92.     return min(_min_b[k][l] , _min_b[k][r - (1 << k) + 1]);
  93. }
  94.  
  95. long long get_min_c(int l , int r){
  96.     if (l > r) return INF;
  97.     int k = _LOG2(r - l + 1);
  98.     return min(_min_c[k][l] , _min_c[k][r - (1 << k) + 1]);
  99. }
  100.  
  101. long long get_min_d(int l , int r){
  102.     if (l > r) return INF;
  103.     int k = _LOG2(r - l + 1);
  104.     return min(_min_d[k][l] , _min_d[k][r - (1 << k) + 1]);
  105. }
  106.  
  107. long long sol(int id){
  108.     long long res = INF;
  109.     long long Max = get_max(1 , id - 1) , Min = get_min(1 , id - 1);
  110.     if (id == n) return Max - Min;
  111.  
  112.     int l = id + 1 , r = n , mid , pos1 = n + 1;
  113.     while (l <= r){
  114.         mid = (l + r) >> 1;
  115.         if (get_min(mid , n) >= Min && get_max(mid , n) <= Max){
  116.             pos1 = mid;
  117.             r = mid - 1;
  118.         }
  119.         else l = mid + 1;
  120.     }
  121.     if (pos1 <= n) res = min(res , a[pos1 - 1].c - a[id].c + Max - Min);
  122.  
  123.     l = id + 1 , r = n;
  124.     int pos2 = id;
  125.     while (l <= r){
  126.         mid = (l + r) >> 1;
  127.         if (get_min(mid , n) <= Min && get_max(mid , n) >= Max){
  128.             pos2 = mid;
  129.             l = mid + 1;
  130.         }
  131.         else r = mid - 1;
  132.     }
  133.     if (pos2 > id) res = min(res , get_min_d(id , pos2 - 1) - a[id].c);
  134.  
  135.     if (pos1 - pos2 <= 1) return res;
  136.     if (get_max(pos2 + 1 , n) > Max){
  137.         res = min(res , get_min_c(pos2 , pos1 - 2) - a[id].c - Min);
  138.         if (pos1 > n)
  139.             res = min(res , a[n].c - a[id].c + Max - Min);
  140.     }
  141.     if (get_min(pos2 + 1 , n) < Min){
  142.         res = min(res , get_min_b(pos2 , pos1 - 2) - a[id].c + Max);
  143.         if (pos1 > n)
  144.             res = min(res , a[n].c - a[id].c + Max - Min);
  145.     }
  146.  
  147.     return res;
  148. }
  149.  
  150. void solve(){
  151.     ktao();
  152.     long long res = INF;
  153.     for (int i = 1 ; i <= n ; ++i){
  154.         res = min(res , sol(i));
  155.     }
  156.  
  157.     cout << res;
  158. }
  159.  
  160. int main(){
  161. //    freopen("difmax.inp" , "r" , stdin);
  162. //    freopen("difmax.out" , "w" , stdout);
  163.     faster;
  164.     inp();
  165.     solve();
  166.     return 0;
  167. }
  168.  
Success #stdin #stdout 0s 7564KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
10000000000000000
https://ideone.com/WAl3oe
language:
C++14 (gcc 8.3)
created:
7 hours 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!