Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define NguyenDangQuan the_author
- #define my_heart love_you_to_the_moon_and_back
- #include <bits/stdc++.h>
- #define pb push_back
- #define ld long double
- #define ll long long
- #define ull unsigned long long
- #define float double
- using namespace std;
- int typetest;
- inline void fastIOfileinput(){
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- typetest = 0;
- }
- const int N = 1e5 + 3;
- int n;
- using floats = float*;
- float a[N], b[N], c[N];
- bool lef(const float& a, const float &b){
- return a > b;
- }
- void Enter(){
- cin >> n;
- for(int i = 1; i <= n; ++i){
- cin >> a[i] >> b[i];
- }
- sort(a + 1, a + n + 1, lef);
- sort(b + 1, b + n + 1, lef);
- }
- void sub1(){
- float ans = 0;
- for(int i = 1; i <= n; ++i)
- for(int j = 1; j <= n; ++j)
- ans = max(ans, min(a[i] - i - j, b[j] - i - j));
- cout << ans;
- }
- void sub2(){
- int minn[N];
- float ans = 0;
- minn[1] = 1;
- for(int i = 2; i <= n; ++i)
- if(c[i] > c[minn[i - 1]])
- minn[i] = i;
- else
- minn[i] = minn[i - 1];
- for(int i = 1; i <= n; ++i){
- int piv = min(n, int(a[i] - i));
- int l = 0, m, h = piv;
- while(l <= h){
- m = (l + h) / 2;
- if(b[m] < a[i]) l = m + 1;
- else h = m - 1;
- }
- if(h > 0)
- ans = max(ans, c[minn[h]] - i);
- if(l <= piv)
- ans = max(ans, a[i] - i - l);
- }
- cout << ans;
- }
- void solve(){
- for(int i = 1; i <= n; ++i){
- a[i] += a[i - 1];
- b[i] += b[i - 1];
- c[i] = b[i];
- c[i] -= i;
- }
- cout << fixed << setprecision(4);
- //if(n <= 1000)
- // sub1();
- //else
- sub2();
- }
- main(){
- fastIOfileinput();
- if(typetest){
- int t;
- cin >> t;
- while(t--){
- Enter();
- solve();
- }
- }
- else{
- Enter();
- solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment