Advertisement
Guest User

Untitled

a guest
Nov 17th, 2019
262
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.15 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement