Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<fstream>
- #include<string>
- #include<vector>
- #include<utility>
- #include<algorithm>
- #include<climits>
- #include<set>
- #include<map>
- #include<cmath>
- #include<iomanip>
- #include<iterator>
- #include<queue>
- #include<stack>
- #include<cctype>
- #include<deque>
- #include<time.h>
- #include<bitset>
- //by Skeef79
- //НЕ ИСПОЛЬЗУЙ endl, есть свой en!!
- //Иногда нужно не просто придумывать решение, а метматически расписать систему уравнений
- //для задач с cin/cout в большом кол-ве - gnu , иначе вижуалки. А ваще пробуй два если TL
- //для интерактивок - cout<<flush
- // cin.tie и sync_with_stdio убирать для интерактивок
- typedef long long ll;
- typedef long double ld;
- typedef unsigned long long ull;
- #pragma warning(disable : 4996)
- #pragma comment(linker, "/STACK:16777216")
- #define pb push_back
- #define en '\n'
- #define for0(i,n) for(int i = 0;i<n;i++)
- #define for1(i,n) for(int i = 1;i<=n;i++)
- #define all(x) (x).begin(),(x).end()
- #define rall(x) (x).rbegin(),(x).rend()
- #define vec vector
- #define pii pair<int,int>
- #define pll pair<ll,ll>
- using namespace std;
- const int INF = 2000000000;
- const ll LINF = 2000000000000000000;
- template<typename T> void print(vector<T>& a)
- {
- for (int i = 0; i < a.size(); i++)
- cout << a[i] << ' ';
- }
- template<typename T> void print(deque<T>& a)
- {
- for (int i = 0; i < a.size(); i++)
- cout << a[i] << ' ';
- }
- template<typename T> void print(vector<vector<T>>& a)
- {
- for (int i = 0; i < a.size(); i++)
- {
- for (int j = 0; j < a[i].size(); j++)
- cout << a[i][j] << ' ';
- cout << en;
- }
- }
- template <typename T> void input(vector<T>& a)
- {
- for (int i = 0; i < a.size(); i++)
- cin >> a[i];
- }
- template<typename T> void input(deque<T>& a)
- {
- for (int i = 0; i < a.size(); i++)
- cin >> a[i];
- }
- template<typename T> void input(vector<vector<T>>& a)
- {
- for (int i = 0; i < a.size(); i++)
- for (int j = 0; j < a[i].size(); j++)
- cin >> a[i][j];
- }
- struct fraction
- {
- ll a, b;
- };
- ll gcd(ll a, ll b)
- {
- while (b)
- {
- a %= b;
- swap(a, b);
- }
- return a;
- }
- void simplify(fraction &x)
- {
- ll gcd_ = gcd(x.a, x.b);
- x.a /= gcd_;
- x.b /= gcd_;
- }
- fraction min(fraction x, fraction y)
- {
- ll a1 = x.a * y.b;
- ll a2 = y.a * x.b;
- if (a1 < a2)
- return x;
- else
- return y;
- }
- struct band
- {
- ll l, r;
- };
- bool is_intersect(band x, band y)
- {
- if (x.r > y.l)
- return true;
- return false;
- }
- bool cmp(band a, band b)
- {
- return a.l < b.l || a.l == b.l && a.r < b.r;
- }
- bool comp(band a, band b)
- {
- return (a.r - a.l) < (b.r - b.l) || ((a.r - a.l) == (b.r - b.l) && (a.l < b.l) );
- }
- void solve()
- {
- int n;
- cin >> n;
- vector<band> a(n);
- ll minlen = INF;
- for (int i = 0; i < n; i++)
- {
- cin >> a[i].l >> a[i].r;
- minlen = min(minlen, a[i].r - a[i].l);
- }
- sort(all(a), cmp);
- int i = 0;
- fraction ans;
- ans.a = minlen;
- ans.b = 1;
- vector<vector<band>> comps;
- while (i < n)
- {
- int cnt = 1;
- vector<band> tek;
- tek.pb(a[i]);
- while (i<n-1 && is_intersect(a[i], a[i + 1]))
- {
- i++;
- tek.pb(a[i]);
- }
- comps.pb(tek);
- i++;
- }
- //for (auto to : comps)
- //{
- // for (auto v : to)
- // {
- // cout << v.l <<' '<< v.r << en;
- // }
- // cout << "NEXT" << en;
- //}
- for (auto &to : comps)
- {
- sort(all(to), comp);
- set<pair<pll, ll>>stl;
- set<pair<pll, ll>> str;
- stl.insert({ {to[0].l,to[0].r},1 });
- str.insert({ {to[0].r,to[0].l} ,1 });
- for (int i = 1; i < to.size(); i++)
- {
- auto it1 = str.upper_bound({ {to[i].l,0},0 });
- auto it2 = stl.upper_bound({ {to[i].l,0},0 });
- pair<pll, ll> to_add;
- to_add.first.first = to[i].l;
- to_add.first.second = to[i].r;
- to_add.second = 1;
- if (it1 != str.end())
- {
- ll l, r,cnt;
- r = it1->first.first;
- l = it1->first.second;
- cnt = it1->second;
- fraction temp;
- temp.a = to[i].r - l;
- temp.b = (cnt + 1);
- ans = min(ans, temp);
- to_add.first.first = l;
- to_add.second += cnt;
- str.erase(it1);
- }
- if (it2 != stl.end())
- {
- ll l, r, cnt;
- l = it1->first.first;
- r = it1->first.second;
- cnt = it1->second;
- fraction temp;
- temp.a = r - to[i].l;
- temp.b = (cnt + 1);
- ans = min(ans, temp);
- to_add.first.second = r;
- to_add.second += cnt;
- stl.erase(it2);
- }
- fraction temp;
- temp.a = to_add.first.second-to_add.first.first;
- temp.b = (to_add.second);
- ans = min(ans,temp);
- stl.insert(to_add);
- pair<pll, ll> to_add2;
- to_add2.first.first = to_add.first.second;
- to_add2.first.second = to_add.first.first;
- to_add2.second = to_add.second;
- str.insert(to_add2);
- }
- }
- cout << ans.a << '/' << ans.b;
- }
- int main()
- {
- ios::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- #endif
- //freopen("journey.in", "r", stdin);
- //freopen("journey.out", "w", stdout);
- int tst = 1;
- //cin >> tst;
- while (tst--)
- solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement