Time Limit: 2500MS Memory Limit: 32768KB 64bit IO Format: %I64d & %I64u

Status

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 in[latex]T(1 \leq T \leq 100)[/latex](the data for [latex]N > 100[/latex] less than 11 cases),indicating the number of test cases.
Each test case begins with an integer [latex]N(1 \leq N \leq 10^5)[/latex],indicating the number of lines.
Next N lines contains two integers [latex]X_i[/latex] and [latex]Y_i(1 \leq X_i \leq Y_i \leq 10^9)[/latex],describing 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


线段树区间更新+离散化模板题。注意输入一定要用scanf!!!!!!!我开始用cin坑了一个小时,一直TLE,一直以为某处写成死循环了_(:зゝ∠)_
PS:貌似能用贪心做
AC代码:
#include <algorithm>
#include <cstring>
#include <cstdio>

#define lson id << 1, l, mid
#define rson id << 1 | 1, mid + 1, r

using namespace std;
int n;
const int maxn = 100000 + 10;
int a[maxn * 2], L[maxn], R[maxn];
struct node
{
	int l, r, lazy, max;
}tree[maxn * 8];
void input()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d%d", &L[i], &R[i]);
}
void build(int id, int l, int r)
{
	tree[id].l = l, tree[id].r = r, tree[id].lazy = tree[id].max = 0;
	if (l == r)
		return;
	int mid = (l + r) >> 1;
	build(lson);
	build(rson);
}
void pushdown(int id)
{
	if (tree[id].lazy)
	{
		tree[id << 1].lazy += tree[id].lazy;
		tree[id << 1].max += tree[id].lazy;
		tree[id << 1 | 1].lazy += tree[id].lazy;
		tree[id << 1 | 1].max += tree[id].lazy;
		tree[id].lazy = 0;
	}
}
void update(int id, int l, int r)
{
	if (tree[id].l == l && tree[id].r == r)
	{
		tree[id].lazy++;
		tree[id].max++;
		return;
	}
	pushdown(id);
	int mid = (tree[id].l + tree[id].r) >> 1;
	if (r <= mid)
		update(id << 1, l, r);
	else if (l > mid)
		update(id << 1 | 1, l, r);
	else
	{
		update(lson);
		update(rson);
	}
	tree[id].max = max(tree[id << 1].max, tree[id << 1 | 1].max);
}
void solve()
{
	for (int i = 0; i < n; i++)
	{
		a[i] = L[i];
		a[i + n] = R[i];
	}
	sort(a, a + 2 * n);
	int cnt = 1;
	for (int i = 1; i < 2 * n; i++)
		if (a[i] != a[i - 1])
			a[cnt++] = a[i];
	build(1, 1, cnt);
	for (int i = 0; i < n; i++)
	{
		int l = lower_bound(a, a + cnt, L[i]) - a + 1,
			r = lower_bound(a, a + cnt, R[i]) - a + 1;
		//cout << l << ' ' << r << endl;
		update(1, l, r);
	}
	printf("%d\n", tree[1].max);
}
int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		input();
		solve();
	}
	return 0;
}

 

分类: ACM/ICPC

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注