| Time Limit: 2500MS | Memory Limit: 32768KB | 64bit IO Format: %I64d & %I64u |
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.
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;
}
0 条评论