SHARE
TWEET

Untitled

a guest Nov 17th, 2019 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. #include<fstream>
  3. #include<string>
  4. #include<vector>
  5. #include<utility>
  6. #include<algorithm>
  7. #include<climits>
  8. #include<set>
  9. #include<map>
  10. #include<cmath>
  11. #include<iomanip>
  12. #include<iterator>
  13. #include<queue>
  14. #include<stack>
  15. #include<cctype>
  16. #include<deque>
  17. #include<time.h>
  18. #include<bitset>
  19.  
  20. //by Skeef79
  21.  
  22. //НЕ ИСПОЛЬЗУЙ endl, есть свой en!!
  23. //Иногда нужно не просто придумывать решение, а метматически расписать систему уравнений
  24. //для задач с cin/cout в большом кол-ве - gnu , иначе вижуалки. А ваще пробуй два если TL
  25.  
  26. //для интерактивок - cout<<flush
  27. // cin.tie и sync_with_stdio убирать для интерактивок
  28.  
  29. typedef long long ll;
  30. typedef long double ld;
  31. typedef unsigned long long ull;
  32.  
  33. #pragma warning(disable : 4996)
  34. #pragma comment(linker, "/STACK:16777216")
  35. #define pb push_back
  36. #define en '\n'
  37. #define for0(i,n) for(int i = 0;i<n;i++)
  38. #define for1(i,n) for(int i = 1;i<=n;i++)
  39. #define all(x) (x).begin(),(x).end()
  40. #define rall(x) (x).rbegin(),(x).rend()
  41. #define vec vector
  42. #define pii pair<int,int>
  43. #define pll pair<ll,ll>
  44.  
  45. using namespace std;
  46.  
  47. const int INF = 2000000000;
  48. const ll LINF = 2000000000000000000;
  49.  
  50. template<typename T> void print(vector<T>& a)
  51. {
  52.     for (int i = 0; i < a.size(); i++)
  53.         cout << a[i] << ' ';
  54. }
  55.  
  56. template<typename T> void print(deque<T>& a)
  57. {
  58.     for (int i = 0; i < a.size(); i++)
  59.         cout << a[i] << ' ';
  60. }
  61.  
  62. template<typename T> void print(vector<vector<T>>& a)
  63. {
  64.     for (int i = 0; i < a.size(); i++)
  65.     {
  66.         for (int j = 0; j < a[i].size(); j++)
  67.             cout << a[i][j] << ' ';
  68.         cout << en;
  69.     }
  70. }
  71.  
  72. template <typename T> void input(vector<T>& a)
  73. {
  74.     for (int i = 0; i < a.size(); i++)
  75.         cin >> a[i];
  76. }
  77.  
  78. template<typename T> void input(deque<T>& a)
  79. {
  80.     for (int i = 0; i < a.size(); i++)
  81.         cin >> a[i];
  82. }
  83.  
  84. template<typename T> void input(vector<vector<T>>& a)
  85. {
  86.     for (int i = 0; i < a.size(); i++)
  87.         for (int j = 0; j < a[i].size(); j++)
  88.             cin >> a[i][j];
  89. }
  90.  
  91. struct fraction
  92. {
  93.     ll a, b;
  94. };
  95.  
  96. ll gcd(ll a, ll b)
  97. {
  98.     while (b)
  99.     {
  100.         a %= b;
  101.         swap(a, b);
  102.     }
  103.     return a;
  104. }
  105.  
  106. void simplify(fraction &x)
  107. {
  108.     ll gcd_ = gcd(x.a, x.b);
  109.     x.a /= gcd_;
  110.     x.b /= gcd_;
  111. }
  112.  
  113. fraction min(fraction x, fraction y)
  114. {
  115.     ll a1 = x.a * y.b;
  116.     ll a2 = y.a * x.b;
  117.     if (a1 < a2)
  118.         return x;
  119.     else
  120.         return y;
  121. }
  122.  
  123. struct band
  124. {
  125.     ll l, r;
  126. };
  127.  
  128. bool is_intersect(band x, band y)
  129. {
  130.     if (x.r > y.l)
  131.         return true;
  132.    
  133.     return false;
  134.  
  135. }
  136.  
  137. bool cmp(band a, band b)
  138. {
  139.     return a.l < b.l || a.l == b.l && a.r < b.r;
  140. }
  141.  
  142. bool comp(band a, band b)
  143. {
  144.     return (a.r - a.l) < (b.r - b.l) || ((a.r - a.l) == (b.r - b.l) && (a.l < b.l) );
  145. }
  146.  
  147. void solve()
  148. {
  149.     int n;
  150.     cin >> n;
  151.     vector<band> a(n);
  152.    
  153.     ll minlen = INF;
  154.  
  155.     for (int i = 0; i < n; i++)
  156.     {
  157.         cin >> a[i].l >> a[i].r;
  158.         minlen = min(minlen, a[i].r - a[i].l);
  159.     }
  160.    
  161.     sort(all(a), cmp);
  162.  
  163.     int i = 0;
  164.     fraction ans;
  165.     ans.a = minlen;
  166.     ans.b = 1;
  167.    
  168.     vector<vector<band>> comps;
  169.  
  170.     while (i < n)
  171.     {
  172.         int cnt = 1;
  173.         vector<band> tek;
  174.         tek.pb(a[i]);
  175.         while (i<n-1 && is_intersect(a[i], a[i + 1]))
  176.         {
  177.             i++;
  178.             tek.pb(a[i]);
  179.         }
  180.         comps.pb(tek);
  181.         i++;
  182.     }
  183.  
  184.     //for (auto to : comps)
  185.     //{
  186.     //  for (auto v : to)
  187.     //  {
  188.     //      cout << v.l <<' '<< v.r << en;
  189.     //  }
  190.     //  cout << "NEXT" << en;
  191.  
  192.     //}
  193.  
  194.  
  195.     for (auto &to : comps)
  196.     {
  197.         sort(all(to), comp);
  198.  
  199.         set<pair<pll, ll>>stl;
  200.         set<pair<pll, ll>> str;
  201.  
  202.         stl.insert({ {to[0].l,to[0].r},1 });
  203.         str.insert({ {to[0].r,to[0].l} ,1 });
  204.  
  205.         for (int i = 1; i < to.size(); i++)
  206.         {
  207.             auto it1 = str.upper_bound({ {to[i].l,0},0 });
  208.             auto it2 = stl.upper_bound({ {to[i].l,0},0 });
  209.            
  210.             pair<pll, ll> to_add;
  211.  
  212.             to_add.first.first = to[i].l;
  213.             to_add.first.second = to[i].r;
  214.             to_add.second = 1;
  215.  
  216.             if (it1 != str.end())
  217.             {
  218.                 ll l, r,cnt;
  219.                 r = it1->first.first;
  220.                 l = it1->first.second;
  221.                 cnt = it1->second;
  222.            
  223.                 fraction temp;
  224.                 temp.a = to[i].r - l;
  225.                 temp.b = (cnt + 1);
  226.                 ans = min(ans, temp);
  227.                 to_add.first.first = l;
  228.                 to_add.second += cnt;
  229.                 str.erase(it1);
  230.  
  231.             }
  232.             if (it2 != stl.end())
  233.             {
  234.                 ll l, r, cnt;
  235.                 l = it1->first.first;
  236.                 r = it1->first.second;
  237.                 cnt = it1->second;
  238.                 fraction temp;
  239.                 temp.a = r - to[i].l;
  240.                 temp.b = (cnt + 1);
  241.                 ans = min(ans, temp);
  242.                 to_add.first.second = r;
  243.                 to_add.second += cnt;
  244.  
  245.                 stl.erase(it2);
  246.             }
  247.  
  248.             fraction temp;
  249.             temp.a = to_add.first.second-to_add.first.first;
  250.             temp.b = (to_add.second);
  251.             ans = min(ans,temp);
  252.             stl.insert(to_add);
  253.             pair<pll, ll> to_add2;
  254.             to_add2.first.first = to_add.first.second;
  255.             to_add2.first.second = to_add.first.first;
  256.             to_add2.second = to_add.second;
  257.             str.insert(to_add2);
  258.         }
  259.     }
  260.  
  261.     cout << ans.a << '/' << ans.b;
  262. }
  263.  
  264.  
  265.  
  266.  
  267.  
  268.  
  269. int main()
  270. {
  271.     ios::sync_with_stdio(false);
  272.     cin.tie(0);
  273.     cout.tie(0);
  274.  
  275. #ifdef _DEBUG
  276.     freopen("input.txt", "r", stdin);
  277. #endif
  278.  
  279.     //freopen("journey.in", "r", stdin);
  280.     //freopen("journey.out", "w", stdout);
  281.  
  282.     int tst = 1;
  283.     //cin >> tst;
  284.     while (tst--)
  285.         solve();
  286.  
  287. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top