ACM-ICPC 2018 徐州赛区网络预赛 G. Trace (思维，贪心)

Trace

问答问题反馈

只看题面

  • 35.78%
  • 1000ms
  • 262144K

There's a beach in the first quadrant. And from time to time, there are sea waves. A wave ( xx , yy ) means the wave is a rectangle whose vertexes are ( 00 , 00 ), ( xx , 00 ), ( 00 , yy ), ( xx , yy ). Every time the wave will wash out the trace of former wave in its range and remain its own trace of ( xx , 00 ) -> ( xx , yy ) and ( 00 , yy ) -> ( xx , yy ). 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 \le 50000)n(n≤50000).

The next nn lines，each contains two numbers xx yy ,( 0 < x0<x , y \le 10000000y≤10000000 )，the ii-th line means the ii-th second there comes a wave of ( xx , yy ), it's guaranteed that when 1 \le i1≤i , j \le nj≤n ，x_i \le x_jx**i≤x**j and y_i \le y_jy**i≤y**j 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=10

样例输入复制

3
1 4
4 1
3 3

样例输出复制

10

题目来源

[ACM-ICPC 2018 徐州赛区网络预赛](https://nanti.jisuanke.com/acm?kw=ACM-ICPC 2018 徐州赛区网络预赛)

题意：

n波矩形海浪，每次都会在沙滩上留下痕迹，求最后的痕迹长度。

思路：

因为题里保证了不会有一个海浪被另外一个海浪完全覆盖的情况，所以n波海浪都会凸出去，并且没有两个波的x会相等，y也是不会相等。如果画个图看，就会发现我们只要逆序的处理每一个横坐标，它对答案的贡献就是去找离它最近的并且比它小的横坐标累加这两个坐标的差值即可，纵坐标亦是如此。

我们用set <int> 这个STL容器就可以很容易的解决。 </int>

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
#define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))
#define du2(a,b) scanf("%d %d",&(a),&(b))
#define du1(a) scanf("%d",&(a));
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) {a %= MOD; if (a == 0ll) {return 0ll;} ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;}
void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}

inline void getInt(int* p);
const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
int x, y;
set<int> sx, sy;
pii a[maxn];
int main()
{
    //freopen("D:\\code\\text\\input.txt","r",stdin);
    //freopen("D:\\code\\text\\output.txt","w",stdout);
    int n;
    gbtb;
    cin >> n;
    ll ans = 0ll;
    sx.insert(0);
    sy.insert(0);

    repd(i, 1, n)
    {
        cin >> x >> y;
        a[i].fi = x;
        a[i].se = y;
    }
    for (int i = n; i >= 1; --i)
    {
        x = a[i].fi;
        y = a[i].se;

        auto it = sx.upper_bound(x);
        it--;
        ans += 1ll * (x - (*it));

        it = sy.upper_bound(y);
        it--;
        ans += 1ll * (y - (*it));

        sx.insert(x);
        sy.insert(y);
    }

    printf("%lld\n", ans );
    return 0;
}

inline void getInt(int* p) {
    char ch;
    do {
        ch = getchar();
    } while (ch == ' ' || ch == '\n');
    if (ch == '-') {
        *p = -(getchar() - '0');
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 - ch + '0';
        }
    }
    else {
        *p = ch - '0';
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 + ch - '0';
        }
    }
}