fork download
copy 
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5.  
  6. //----------MACROS----------
  7. #define int long long int
  8. #define seea(a,x,y) for(int i=x;i<y;i++){cin>>a[i];}
  9. #define seev(v,n) for(int i=0;i<n;i++){int x; cin>>x; v.push_back(x);}
  10. #define sees(s,n) for(int i=0;i<n;i++){int x; cin>>x; s.insert(x);}
  11. #define forn(i, a, b) for(int i=a; i<b; i++)
  12.  
  13. #define vi vector<int>
  14. #define pi pair<int, int>
  15. #define f first
  16. #define s second
  17. #define pb push_back
  18. #define mp make_pair
  19. #define mod 1000000007
  20.  
  21. int t, n, m, k, a, b, c, x, y, q, ans;
  22.  
  23. signed main() {
  24.     ios::sync_with_stdio(false);
  25.     cin.tie(0);
  26.  
  27.     /* freopen("lifeguards.in", "r", stdin); */
  28.     /* freopen("lifeguards.out", "w", stdout); */
  29.  
  30.     cin >> n;
  31.     vector<pi> v(n);
  32.  
  33.     forn(i, 0, n) cin >> a >> b, v[i] = {a, b};
  34.  
  35.     sort(v.begin(), v.end());
  36.  
  37.     /* for (auto x : v) putl(x.f, x.s); */
  38.  
  39.     // Compute the initial cover, when no lifeguards have been removed.
  40.     k = v[0].s - v[0].f;
  41.     forn(i, 1, n) {
  42.         k += v[i].s - v[i].f;
  43.         if (v[i].f <= v[i-1].s) k -= (min(v[i-1].s, v[i].s) - v[i].f);
  44.     }
  45.  
  46.     ans = -1e18;
  47.  
  48.     // One by one remove a lifeguard, and find the current cover
  49.     // in O(1) time using initial cover.
  50.     forn (i, 0, n) {
  51.         int f1 = 0, f2 = 0;
  52.  
  53.         // Find overlap with next interval.
  54.         if (i < n-1)
  55.             f2 = min(v[i+1].s, v[i].s) - v[i+1].f;
  56.  
  57.         // Find overlap with prev interval.
  58.         if (i > 0)
  59.             f1 = min(v[i].s, v[i-1].s) - v[i].f;
  60.  
  61.         // Compute cover with this interval removed.
  62.         x = k + f1 + f2 - (v[i].s - v[i].f); 
  63.  
  64.         ans = max(ans, x);
  65.     }
  66.  
  67.     cout << ans << endl;
  68.     return 0;
  69. }
  70.  
  71.  
Success #stdin #stdout 0s 5668KB
comments (?)
stdin
copy 
4
1 10
3 15
8 12
11 13
stdout
copy 
16
https://ideone.com/Sw7DJa
language:
C++ (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!