Dang_Quan_10_Tin

Untitled

Jun 28th, 2020
238
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.66 KB | None | 0 0
  1. #define NguyenDangQuan the_author
  2. #define my_heart love_you_to_the_moon_and_back
  3.  
  4. #include <bits/stdc++.h>
  5. #define pb push_back
  6. #define ld long double
  7. #define ll long long
  8. #define ull unsigned long long
  9. #define float double
  10. using namespace std;
  11.  
  12. int typetest;
  13. inline void fastIOfileinput(){
  14.     ios::sync_with_stdio(0);
  15.     cin.tie(0);
  16.     cout.tie(0);
  17.     typetest = 0;
  18. }
  19.  
  20. const int N = 1e5 + 3;
  21. int n;
  22. using floats = float*;
  23. float a[N], b[N], c[N];
  24.  
  25. bool lef(const float& a, const float &b){
  26.     return a > b;
  27. }
  28.  
  29. void Enter(){
  30.     cin >> n;
  31.     for(int i = 1; i <= n; ++i){
  32.         cin >> a[i] >> b[i];
  33.     }
  34.     sort(a + 1, a + n + 1, lef);
  35.     sort(b + 1, b + n + 1, lef);
  36. }
  37.  
  38. void sub1(){
  39.     float ans = 0;
  40.     for(int i = 1; i <= n; ++i)
  41.         for(int j = 1; j <= n; ++j)
  42.             ans = max(ans, min(a[i] - i - j, b[j] - i - j));
  43.     cout << ans;
  44. }
  45.  
  46. void sub2(){
  47.     int minn[N];
  48.     float ans = 0;
  49.     minn[1] = 1;
  50.     for(int i = 2; i <= n; ++i)
  51.         if(c[i] > c[minn[i - 1]])
  52.             minn[i] = i;
  53.         else
  54.             minn[i] = minn[i - 1];
  55.     for(int i = 1; i <= n; ++i){
  56.         int piv = min(n, int(a[i] - i));
  57.         int l = 0, m, h = piv;
  58.         while(l <= h){
  59.             m = (l + h) / 2;
  60.             if(b[m] < a[i]) l = m + 1;
  61.             else h = m - 1;
  62.         }
  63.         if(h > 0)
  64.             ans = max(ans, c[minn[h]] - i);
  65.         if(l <= piv)
  66.             ans = max(ans, a[i] - i - l);
  67.     }
  68.     cout << ans;
  69. }
  70.  
  71. void solve(){
  72.     for(int i = 1; i <= n; ++i){
  73.         a[i] += a[i - 1];
  74.         b[i] += b[i - 1];
  75.         c[i] = b[i];
  76.         c[i] -= i;
  77.     }
  78.     cout << fixed << setprecision(4);
  79.     //if(n <= 1000)
  80.     //  sub1();
  81.     //else
  82.         sub2();
  83. }
  84.  
  85. main(){
  86.     fastIOfileinput();
  87.     if(typetest){
  88.         int t;
  89.         cin >> t;
  90.         while(t--){
  91.             Enter();
  92.             solve();
  93.         }
  94.     }
  95.     else{
  96.         Enter();
  97.         solve();
  98.     }
  99. }
Advertisement
Add Comment
Please, Sign In to add comment