快速切题 sgu133.Border 离线

133. Border

time limit per test: 0.25 sec. 
memory limit per test: 4096 KB

 

Along the border between states A and B there are N defence outposts. For every outpost k, the interval [A_k,B_k] which is guarded by it is known. Because of financial reasons, the president of country A decided that some of the outposts should be abandoned. In fact, all the redundant outposts will be abandoned. An outpost i is redundant if there exists some outpost j such that A_j<A_i and B_i<B_j. Your task is to find the number of redundant outposts.

 

Input

The first line of the input will contain the integer number N (1<=N<=16 000). N lines will follow, each of them containing 2 integers: A_k and B_k (0<= A_k < B_k <= 2 000 000 000), separated by blanks. All the numbers A_k will be different. All the numbers B_k will be different.

 

Output

You should print the number of redundant outposts.

 

Sample Input

5
0 10
2 9
3 8
1 15
6 11

Sample Output

3

#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef  long long ll;
typedef pair<ll,ll> P;
P seg[17000];
int n;
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%I64d%I64d",&seg[i].first,&seg[i].second);
    }
    sort(seg,seg+n);
    ll maxn=seg[0].second;
    int cnt=0;
    for(int i=0;i<n;i++){
        if(seg[i].second<maxn)cnt++;
        else maxn=seg[i].second;
    }
    printf("%d\n",cnt);
}