ACM-ICPC 2018 徐州赛区网络预赛 Trace

There's a beach in the first quadrant. And from time to time, there are sea waves. A wave ( xxx , yyy ) means the wave is a rectangle whose vertexes are ( 000 , 000 ), ( xxx , 000 ), ( 000 , yyy ), ( xxx , yyy ). Every time the wave will wash out the trace of former wave in its range and remain its own trace of ( xxx , 000 ) -> ( xxx , yyy ) and ( 000 , yyy ) -> ( xxx , yyy ). Now the toad on the coast wants to know the total length of trace on the coast after n waves. It's guaranteed that a wave will not cover the other completely.

Input

The first line is the number of waves n(n≤50000)n(n \le 50000)n(n≤50000).

The next nnn lines，each contains two numbers xxx yyy ,( 0<x0 < x0<x , y≤10000000y \le 10000000y≤10000000 )，the iii-th line means the iii-th second there comes a wave of ( xxx , yyy ), it's guaranteed that when 1≤i1 \le i1≤i , j≤nj \le nj≤n ，xi≤xjx_i \le x_jxi​≤xj​ and yi≤yjy_i \le y_jyi​≤yj​ don't set up at the same time.

Output

An Integer stands for the answer.

Hint：

As for the sample input, the answer is 3+3+1+1+1+1=103+3+1+1+1+1=103+3+1+1+1+1=10

样例输入复制

3
1 4
4 1
3 3

样例输出复制

10

题目来源

ACM-ICPC 2018 徐州赛区网络预赛

思路来源

ACM-ICPC 2018 徐州赛区网络预赛 G. Trace

相关资料

C/C++——set的基本操作总结

C++迭代器 iterator

关于lower_bound( )和upper_bound( )的常见用法

解题思路

正着模拟求解，显然很复杂，容易出错。

因为不会完全覆盖之前的浪花。所以倒序求解，是不会有覆盖产生的。

不断地向set里加数字。因为不完全覆盖，所以，一定有维护了单调递增的性质。

#include<stdio.h>
#include<set>
using namespace std;
#define maxn 50005
int n;
long long x[maxn],y[maxn];
long long solve(long long *a)
{
    set<long long>temp;
    set<long long>::iterator it;
    long long answer=0;
    for(int i=n;i>=1;i--)
    {
        it=temp.lower_bound(a[i]);
        if(it==temp.begin())
        {
            answer+=a[i];
        }
        else
        {
            it--;
            answer+=a[i]-(*it);
        }
        temp.insert(a[i]);
    }
    return answer;
}

int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%lld%lld",&x[i],&y[i]);
        }
        printf("%lld\n",solve(x)+solve(y));
    }
    return 0;
}