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 条评论