题目

校门外原先有一排树，后来因为建地铁都被拔掉了，现在只剩下树坑了。但是现在为了美化环境，要重新进行栽树，并且为了考虑经费，一个树坑里面可以栽多棵树。每个树坑的坐标都是整数点，每次栽树的时候播种的范围是一个区间，区间的端点也都是整数点。 给定 n次播种的区间，最后图灵王会去清点这棵树，但是最近他业务繁忙有些头疼，感觉已经不会数数了。现在他想让你统计一下，有多少树坑栽种一棵树、二棵树、三棵树...... , 当然可能栽种 i 棵树的树坑不存在，那样就不用输出这个0。

输入

输入第一行包含一个正整数n，代表播种的次数 接下来包括n行，每行两个端点代表播种的区间

输出

输出包含若干行，每行输出的格式为

栽种树的数量: 树坑的数量

当然如果树坑的数量为0则无需输出

样例1

输入数据 1

4
3 9
0 5
6 8
7 12

输出数据 1

1:6
2:5
3:2

样例2

输入数据 2

3
3 9
3 9
3 9

输出数据 2

3:7

样例3

输入数据 3

2
3 4
4 7

输出数据 3

1:4
2:1

数据

$50\%$的数据保证，$n≤1000,1≤l≤r≤1000$

$100\%$的数据保证，$n≤10^6,1≤l≤r≤10^9$

My code:

#include<bits/stdc++.h>
using namespace std;
int n,t[1000005],l,r,cnt=1;
struct Node{
	int num,id;
}a[2000005];
bool cmp(Node x,Node y){
	return x.num<y.num;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n*2;i+=2){
		scanf("%d%d",&l,&r);
		a[i].num=l;
		a[i].id=1;
		a[i+1].num=r;
		a[i+1].id=-1;
	}
	sort(a+1,a+n*2+1,cmp);
	for(int i=2;i<=n*2;i++){
		cnt+=a[i].id;
		if((a[i].id==-1&&a[i-1].id==-1)||(a[i].id==1&&a[i-1].id==1))	t[cnt]+=a[i].num-a[i-1].num;
		if(a[i].id==1&&a[i-1].id==-1)	t[cnt]+=a[i].num-a[i-1].num+1;
		if(a[i].id==-1&&a[i-1].id==1)	t[cnt]+=a[i].num-a[i-1].num-1;
	}
	for(int i=1;i<=1000000;i++){
		if(t[i])	printf("%d:%d\n",i,t[i]);
	}
	return 0;
}