AC CODE

AC code

#include <cstdio>
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
const int maxn=100010;
int h[maxn],x[maxn],rx[maxn],rh[maxn];
bool cmp1(int a,int b)
{
    return x[a]<x[b];
}
bool cmp2(int a,int b)
{
    return h[a]>h[b];
}
int s[maxn],sum;
int n,ref[maxn],ans;
set <int> ms;
int main()
{
    scanf("%d",&n);
    int i,j;
    for(i=1;i<=n;i++)    scanf("%d%d",&h[i],&x[i]),rx[i]=rh[i]=i;
        //rx，rh存储的其实是编号，我们是在将编号排序
    sort(rx+1,rx+n+1,cmp1);
    for(i=1;i<=n;i++)
    {
        ref[i]=x[rx[i]];
        x[rx[i]]=i;
    }
    sort(rh+1,rh+n+1,cmp2);
    set<int>::iterator it;
    for(i=1;i<=n;i++)
    {
        it=ms.lower_bound(x[rh[i]]);
        if(it!=ms.begin()&&!ms.empty())
        {
            it--;
            j=rx[*it];
            if(ref[x[rh[i]]]-ref[x[j]]<=min(h[rh[i]],h[j]))
            {
                s[x[j]]++;
                s[x[rh[i]]]--;
            }
        }
        it=ms.upper_bound(x[rh[i]]);
        if(it!=ms.end())
        {
            j=rx[*it];
            if(ref[x[j]]-ref[x[rh[i]]]<=min(h[rh[i]],h[j]))
            {
                s[x[rh[i]]]++;
                s[x[j]]--;
            }
        }
        ms.insert(x[rh[i]]);
    }
    for(i=1;i<=n;i++)
    {
        ans+=(sum>0)*(ref[i]-ref[i-1]);
        sum+=s[i];
    }
    printf("%d",ans);
    return 0;
}