lines
Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 330 Accepted Submission(s): 155
Problem Description
John has several lines. The lines are covered on the X axis. Let A is a point which is covered by the most lines. John wants to know how many lines cover A.
Input
The first line contains a single integer
T(1≤T≤100) (the
data forN>100
less than 11 cases),indicating the number of test cases.
Each test case begins with an integerN(1≤N≤105) ,indicating
the number of lines.
Next N lines contains two integersXi
andYi(1≤Xi≤Yi≤109) ,describing
a line.
data for
less than 11 cases),indicating the number of test cases.
Each test case begins with an integer
the number of lines.
Next N lines contains two integers
and
a line.
Output
For each case, output an integer means how many lines cover A.
Sample Input
2 5 1 2 2 2 2 4 3 4 5 1000 5 1 1 2 2 3 3 4 4 5 5
Sample Output
3 1
Source
Recommend
Statistic | Submit | Discuss
| Note
比赛时一开始用线段树WA了，然后树状数组过的，赛后听某牛说可以O(n)，然后仔细想了下，比如现在要在[l，r]上覆盖一次，那么我们可以在s[l]上+1，s[r + 1] 上 - 1，记录覆盖次数，然后for一遍，当前的s[i] 加上 s[i - 1]就是i这个点被覆盖的次数，因为有s[r + 1] --，所以此方案是合理的，数据太大可以离散化一下
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int xis[N << 1];
int po[N << 1];
struct node
{
int l, r;
}lines[N];
int main()
{
int t, n, cnt, res, ans;
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
map <int, int> newx;
memset (xis, 0, sizeof(xis));
newx.clear();
cnt = 0;
res = 0;
for (int i = 0; i < n; ++i)
{
scanf("%d%d", &lines[i].l, &lines[i].r);
po[cnt++] = lines[i].l;
po[cnt++] = lines[i].r;
}
sort (po, po + cnt);
for (int i = 0; i < cnt; ++i)
{
if (i == 0)
{
newx[po[i]] = ++res;
}
else if(po[i] == po[i - 1])
{
newx[po[i]] = newx[po[i - 1]];
}
else
{
newx[po[i]] = ++res;
}
}
for (int i = 0; i < n; ++i)
{
int l = newx[lines[i].l];
int r = newx[lines[i].r];
xis[l]++;
xis[r + 1]--;
}
ans = 0;
for (int i = 1; i <= res; ++i)
{
xis[i] += xis[i - 1];
if (ans < xis[i])
{
ans = xis[i];
}
}
printf("%d\n", ans);
}
return 0;
}