2014
11-27

# Judge Segments

There are many segments and many points. For each pair of points, we get a segment between them. Calculate how many given segments contains the segment. If two points are in the same location, the result is how many given segments contains the point.
Note: Segment [1,10] contains the segment made by point 1 and point 10.

Multi-testcase. An integer t indicate the number of test cases. t is less than 20.
For each test case, n and m ( 0 <= n <= 100000,0 <= m <= 500 ) indicate the number of segments and the number of points.
Following n lines, each line input two numbers a, b ( 0 <= a < b <= 100000 ) indicate the given segments.
Following m numbers, c ( 0 <= c <= 10^6 ) indicate all the points. All the points are given in non-decreasing order.

Multi-testcase. An integer t indicate the number of test cases. t is less than 20.
For each test case, n and m ( 0 <= n <= 100000,0 <= m <= 500 ) indicate the number of segments and the number of points.
Following n lines, each line input two numbers a, b ( 0 <= a < b <= 100000 ) indicate the given segments.
Following m numbers, c ( 0 <= c <= 10^6 ) indicate all the points. All the points are given in non-decreasing order.

2
2 4
2 5
1 4
1 2 4 5
2 4
1 4
6 9
1 4 6 9

Case 1:
1 1 1 0
1 2 2 1
1 2 2 1
0 1 1 1

Case 2:
1 1 0 0
1 1 0 0
0 0 1 1
0 0 1 1

//扫描线求线段覆盖
//For each
pair of points, we get a segment between them. Calculate how many
given
//segments
contains the segment. If two points are in the same location, the
result
//is how
many given segments contains the point.

//学会总结规律，避免重复计算以避免TLE，坚决拒绝CE，RE，PE等弱智罚时错误！！！
############################################Source
Code：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using
namespace std;
struct
segment
{
int s, e;
bool operator <(const segment
&t)const
{
return e>t.e;
}
}seg[100005];
int
p[505], n, m;
int
num[505][505];
bool
cmp(segment a, segment b)
{
if(a.s==b.s)return a.e<b.e;
return a.s<b.s;
}
int
main()
{
//freopen(“J.in”, “r”, stdin);
//freopen(“out.txt”, “w”, stdout);
int t, ca, i, j, k;
scanf(“%d”, &ca);
for(t=1; t<=ca; t++)
{
scanf(“%d%d”, &n, &m);
for(i=0; i<n; i++)
scanf(“%d%d”, &seg[i].s,
&seg[i].e);
sort(seg, seg+n, cmp);
for(i=0; i<m; i++)
scanf(“%d”, &p[i]);
memset(num, 0, sizeof(num));
segment ts;
k=0;
for(i=0; i<m; i++)
{
priority_queue<segment>
q;//优先队列里按结尾排
for(; k<n; k++)//压入没覆盖i-1点但是覆盖i点的线段
{
if(seg[k].e<p[i])continue;
if(seg[k].s>p[i])break;
q.push(seg[k]);
}
for(j=i; j<m; j++)
{
if(i!=0)num[i][j]=num[i-1][j];//注意应用已知的条件
while(!q.empty())
{
ts=q.top();
if(ts.e>=p[j])break;
q.pop();
}
num[i][j]+=q.size();
num[j][i]=num[i][j];
}
}
printf(“Case %d:\n”, t);
for(i=0; i<m; i++)
{
for(j=0; j<m-1; j++)
printf(“%d “, num[i][j]);
printf(“%d\n”, num[i][j]);
}
printf(“\n”);
}
return 0;
}

1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

2. 站长，你好！
你创办的的网站非常好，为我们学习算法练习编程提供了一个很好的平台，我想给你提个小建议，就是要能把每道题目的难度标出来就好了，这样我们学习起来会有一个循序渐进的过程！

3. 第2题，TCP不支持多播，多播和广播仅应用于UDP。所以B选项是不对的。第2题，TCP不支持多播，多播和广播仅应用于UDP。所以B选项是不对的。