Lifeguards USACO Silver Solution

lifeguards.cpp

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

//----------TEMPLATES----------
template<typename... T>
void see(T&... args) { ((cin >> args), ...);}
template<typename... T>
void put(T&&... args) { ((cout << args << " "), ...);}
template<typename... T>
void putl(T&&... args) { ((cout << args << " "), ...); cout<<"\n";}

//----------MACROS----------
#define int long long int
#define seea(a,x,y) for(int i=x;i<y;i++){cin>>a[i];}
#define seev(v,n) for(int i=0;i<n;i++){int x; cin>>x; v.push_back(x);}
#define sees(s,n) for(int i=0;i<n;i++){int x; cin>>x; s.insert(x);}
#define forn(i, a, b) for(int i=a; i<b; i++)

#define vi vector<int>
#define pi pair<int, int>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define mod 1000000007

int t, n, m, k, a, b, c, x, y, q, ans;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    /* freopen("lifeguards.in", "r", stdin); */
    /* freopen("lifeguards.out", "w", stdout); */
    
    cin >> n;
    vector<pi> v(n);

    forn(i, 0, n) cin >> a >> b, v[i] = {a, b};

    sort(v.begin(), v.end());

    /* for (auto x : v) putl(x.f, x.s); */
  
    // Compute the initial cover, when no lifeguards have been removed.
    k = v[0].s - v[0].f;
    forn(i, 1, n) {
        k += v[i].s - v[i].f;
        if (v[i].f <= v[i-1].s) k -= (min(v[i-1].s, v[i].s) - v[i].f);
    }

    ans = -1e18;
     
    // One by one remove a lifeguard, and find the current cover
    // in O(1) time using initial cover.
    forn (i, 0, n) {
        int f1 = 0, f2 = 0;
        
        // Find overlap with next interval.
        if (i < n-1)
            f2 = min(v[i+1].s, v[i].s) - v[i+1].f;
        
        // Find overlap with prev interval.
        if (i > 0)
            f1 = min(v[i].s, v[i-1].s) - v[i].f;
        
        // Compute cover with this interval removed.
        x = k + f1 + f2 - (v[i].s - v[i].f); 

        ans = max(ans, x);
    }
    
    cout << ans << endl;
    return 0;
}