HDU 5124 lines - dblank

lines

Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1439    Accepted Submission(s): 594

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(1T100)(the data for N>100 less than 11 cases),indicating the number of test cases.
Each test case begins with an integer N(1N105),indicating the number of lines.
Next N lines contains two integers Xi and Yi(1XiYi109),describing a line.

Output
For each case, output an integer means how many lines cover A.

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<vector>
#include<map>
#include<cmath>
#include<fstream>
#include<stack>
using namespace std;
typedef long long ll;
struct node
{
int x, v;
}s[200020];
int cmp(node a, node b)
{
if(a.x == b.x)
return a.v>b.v;
return a.x <b.x;
}
int main()
{
int t, n;
cin>>t;
while(t--)
{
scanf("%d", &n);
for(int i = 0; i<n; i++)
{
scanf("%d", &s[i<<1].x);
s[i<<1].v = 1;
scanf("%d", &s[i<<1|1].x);
s[i<<1|1].v = -1;
}
sort(s, s+2*n, cmp);
int cnt = 0, ans = 0;
for(int i = 0; i<2*n; i++)
{
cnt += s[i].v;
ans = max(cnt , ans);
}
cout<<ans<<endl;
}
}

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<vector>
#include<map>
#include<cmath>
#include<fstream>
using namespace std;
struct node
{
int l,r, maxx, mark;
} s[200200<<2];
int x[200020], k, a[100010], b[100010];
void pushup(int cnt)
{
s[cnt].maxx = max(s[cnt<<1].maxx , s[cnt<<1|1].maxx);
}
void pushdown(int cnt)
{
if(s[cnt].mark)
{
//int l = len - (len/2);
s[cnt<<1].mark += s[cnt].mark ;
s[cnt<<1|1].mark += s[cnt].mark;
s[cnt<<1].maxx += s[cnt].mark;
s[cnt<<1|1].maxx += s[cnt].mark;
s[cnt].mark = 0;
}
}
void build_tree(int l, int r, int cnt)
{
s[cnt].l = l;
s[cnt].r = r;
s[cnt].maxx = 0;
s[cnt].mark = 0;
if(l == r)
return ;
int m= (l+r)>>1;
build_tree(l, m, cnt<<1);
build_tree(m+1, r, cnt<<1|1);
}
void update(int l, int r, int cnt)
{
if(s[cnt].l >= l && s[cnt].r <= r)
{
s[cnt].mark += 1;
s[cnt].maxx += 1;
return ;
}
pushdown(cnt);
int m = (s[cnt].l + s[cnt].r)>>1;
if(l <= m)
update(l, r, cnt<<1);
if(r > m)
update(l, r, cnt<<1|1);
pushup(cnt);
}
int main()
{
int t, n, u, v;
cin>>t;
while(t--)
{
scanf("%d", &n);
k = 0;
for(int i = 1; i<=n; i++)
{
scanf("%d%d", &a[i], &b[i]);
x[k++] = a[i];
x[k++] = b[i];
}
sort(x,x+2*n);
//for(int i = 0; i<2*n; i++)
//      printf("%d ", x[i]);
//  printf("\n");
build_tree(1, 2*n, 1);
for(int i = 1; i<=n; i++)
{
int l = lower_bound(x, x+2*n, a[i]) - x + 1;
int r = lower_bound(x, x+2*n, b[i]) - x + 1;
//  printf("%d %d %d %d\n", l, r, a[i], b[i]);
update(l, r, 1);
}
printf("%d\n", s[1].maxx);
}
return 0;
}