fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define fi first
  4. #define se second
  5. #define all(x) x.begin(), x.end()
  6. #define sz(x) (int)x.size()
  7. #define pb push_back
  8. #define re exit(0);
  9. #define left id<<1
  10. #define right id<<1|1
  11. #define FOR(i, a, b)   for(int i = (a), _b = (b); i <= _b; i++)
  12. #define FORD(i, a, b)  for(int i = (a), _b = (b); i >= _b; i--)
  13. #define LOOP(a)        for(int i = 0, _a = (a); i < _a; i++)
  14.  
  15. #define int long long
  16.  
  17. using namespace std;
  18.  
  19. typedef vector<int> vi;
  20. typedef pair<int, int> pii;
  21. typedef vector<pii> vii;
  22.  
  23. template<typename T> void chkmin(T &x, T y) {if (y < x) x = y;}
  24. template<typename T> void chkmax(T &x, T y) {if (y > x) x = y;}
  25.  
  26. const int mod = 1e9 + 7;
  27. void add(int &a, int b) {
  28.     a += b;
  29.     if (a >= mod) a -= mod;
  30.     if (a < 0) a += mod;
  31. }
  32.  
  33. int _pow(int a, int b) {
  34.    int ans = 1;
  35.    while (b) {
  36.    if (b % 2 == 1) ans = 1ll * ans * a % mod;
  37.         a = 1ll * a * a % mod;
  38.         b /= 2;
  39.    }
  40.    return ans;
  41. }
  42. void rf() {
  43.    freopen("input.inp", "r", stdin);
  44. }
  45.  
  46. //--------------------------------------------------------------------------------------------------------------------------------------
  47.  
  48. const int maxn = 2e5;
  49. const int INF = 2e9;
  50. pair<int, int> a[maxn + 5];
  51. int n, start;
  52. int mx, mn;
  53.  
  54. bool cmp1(pii x, pii y) {
  55.     if (x.se != y.se) return x.se < y.se;
  56.     else return x.fi < y.fi;
  57. }
  58.  
  59.  
  60. bool cmp2(pii x, pii y) {
  61.     if (x.se != y.se) return x.se > y.se;
  62.     else return x.fi > y.fi;
  63. }
  64.  
  65. int calc1() {
  66.     vector<pair<int, int> > v;
  67.     for (int i = 1; i <= n; i++)
  68.         if (a[i].se > start && a[i].fi < start)
  69.             v.push_back(a[i]);
  70.  
  71.     if (v.size() == 0) return 0;
  72.     sort(all(v), cmp1); int m = v.size();
  73.  
  74.     vector<int> suf_min(m + 5, INF);
  75.     suf_min[m] = start;
  76.     for (int i = m - 1; i >= 0; i--) suf_min[i] = min(suf_min[i + 1], v[i].fi);
  77.  
  78.     int res = start - suf_min[0];
  79.     for (int i = 0; i <= m - 1; i++) {
  80.         int x = v[i].se, y = suf_min[i + 1];
  81.         chkmin(res, (x - start) + (start - y));
  82.     }
  83.     return res;
  84. }
  85.  
  86. int calc2() {
  87.     vector<pair<int, int> > v;
  88.     for (int i = 1; i <= n; i++)
  89.         if (a[i].se < start && a[i].fi > start)
  90.             v.push_back(a[i]);
  91.  
  92.     if (v.size() == 0) return 0;
  93.     sort(all(v), cmp2); int m = v.size();
  94.  
  95.     vector<int> suf_max(m + 5, INF);
  96.     suf_max[m] = start;
  97.     for (int i = m - 1; i >= 0; i--) suf_max[i] = max(suf_max[i + 1], v[i].fi);
  98.  
  99.     int res = suf_max[0] - start;
  100.     for (int i = 0; i <= m - 1; i++) {
  101.         int x = v[i].se, y = suf_max[i + 1];
  102.         chkmin(res, (start - x) + (y - start));
  103.     }
  104.     return res;
  105. }
  106.  
  107. signed main() {
  108.     ios::sync_with_stdio(0);
  109.     cin.tie(0);
  110.  
  111.     cin >> n >> start;
  112.     for (int i = 1; i <= n; i++)
  113.         cin >> a[i].fi >> a[i].se;
  114.  
  115.     mn = start, mx = start;
  116.     for (int i = 1; i <= n; i++) {
  117.         chkmin(mn, min(a[i].fi, a[i].se));
  118.         chkmax(mx, max(a[i].fi, a[i].se));
  119.     }
  120.  
  121.     long long res = min(calc1(), calc2());
  122.     res += mx - mn; res *= 2;
  123.  
  124.     cout << res;
  125.  
  126.     return 0;
  127. }
  128.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rgbVcb
language:
C++14 (gcc 8.3)
created:
9 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!