题目描述

小w有m条线段，编号为1到m。

用这些线段覆盖数轴上的n个点，编号为1到n。

第i条线段覆盖数轴上的区间是L[i]，R[i]。

覆盖的区间可能会有重叠，而且不保证m条线段一定能覆盖所有n个点。

现在小w不小心丢失了一条线段，请问丢失哪条线段，使数轴上没被覆盖到的点的个数尽可能少，请输出丢失的线段的编号和没被覆盖到的点的个数。如果有多条线段符合要求，请输出编号最大线段的编号（编号为1到m）。

输入描述:

第一行包括两个正整数n，m(1≤n，m≤10^5)。 接下来m行，每行包括两个正整数L[i]，R[i](1≤L[i]≤R[i]≤n)。

输出描述:

输出一行，包括两个整数a b。 a表示丢失的线段的编号。 b表示丢失了第a条线段后，没被覆盖到的点的个数。

示例1

输入

5 31 34 53 4

输出

3 0

说明

若丢失第1条线段，1和2没被线段覆盖到。 若丢失第2条线段，5没被线段覆盖到。 若丢失第3条线段，所有点都被线段覆盖到了。

示例2

输入

6 21 24 5

输出

2 4

说明

若丢失第1条线段，1，2，3，6没被线段覆盖到。 若丢失第2条线段，3，4，5，6没被线段覆盖到。

#include 
          
           using namespace std;const int maxn=1e5+16;int l[maxn],r[maxn],uncovered,n,m,cur[maxn],C[maxn];int one[maxn],line,ans=0x3f3f3f3f;int main(){    cin>>n>>m;    for(int i=1;i<=m;i++){         scanf("%d%d",l+i,r+i);         cur[l[i]]++,cur[r[i]+1]--;    }    for(int i=1;i<=n;i++){         cur[i]+=cur[i-1];         if(!cur[i])uncovered++;         if(cur[i]==1)C[i]=1;         C[i]+=C[i-1];    }    for(int i=1;i<=m;i++){          int now=C[r[i]]-C[l[i]-1];          if(ans>=now)line=i,ans=now;    }    cout<
           
            <<' '<
            
             <