# Pinball Game 3D

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 1137    Accepted Submission(s): 477

Problem Description

RD is a smart boy and excel in pinball game. However, playing common 2D pinball game for a great number of times results in accumulating tedium.  Recently, RD has found a new type of pinball game, a 3D pinball game. The 3D pinball game space can be regarded as a three dimensional coordinate system containing N balls. A ball can be considered as a point. At the beginning, RD made a shot and hit a ball. The ball hit by RD will move and may hit another ball and the “another ball” may move and hit another another ball, etc. But once a ball hit another ball, it will disappear. RD is skilled in this kind of game, so he is able to control every ball's moving direction. But there is a limitation: if ball A's coordinate is (x1,y1,z1) and ball B's coordinate is (x2,y2,z2), then A can hit B only if x1 <= x2 and y1 <= y2 and z1 <= z2. Now, you should help RD to calculate the maximum number of balls that can be hit and the number of different shooting schemes that can achieve that number. Two schemes are different if the sets of hit balls are not the same. The order doesn't matter.

Input

The first line contains one integer T indicating the number of cases. In each case, the first line contains one integer N indicating the number of balls.  The next N lines each contains three non-negative integer (x, y, z), indicating the coordinate of a ball.  The data satisfies T <= 3, N <= 105, 0 <= x, y, z <= 230, no two balls have the same coordinate in one case.

Output

Print two integers for each case in a line, indicating the maximum number of balls that can be hit and the number of different shooting schemes. As the number of schemes can be quite large, you should output this number mod 230.

Sample Input

```2
3
2 0 0
0 1 0
0 1 1
5
3 0 0
0 1 0
0 0 1
0 2 2
3 3 3```

Sample Output

```2 1
3 2

#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>
using namespace std;

const int maxn=1e5;
const int INF=0x7FFFFFFF;
const int mod = 1 << 30 ;

struct Node
{
int x,y,z;
int id,z2;
}a[maxn+5],b[maxn+5];

int n,e,d[maxn+5];
int cmp(Node a,Node b)
{
if(a.x==b.x&&a.y==b.y)
return a.z<b.z;
else if(a.x==b.x)
return a.y<b.y;
return a.x<b.x;
}
int cmp2(Node a,Node b)
{
return a.z<b.z;
}
struct node
{
int len;
int num;
}dp[maxn+5],c[maxn+5];

int lowbit(int x)
{
return x&(-x);
}
void update(node &term1,node term2)
{
if(term1.len<term2.len)
{
term1=term2;
}
else if(term1.len==term2.len)
term1.num+=term2.num;
}

void insert(int x,node y)
{
for(int i=x;i<=e;i+=lowbit(i))
{
update(c[i],y);
}
}
node sum(int x)
{
node p;
for(int i=x;i>=1;i-=lowbit(i))
{
update(p,c[i]);
}
return p;
}
void del(int x)
{
for(int i=x;i<=e;i+=lowbit(i))
{
c[i].len=0;
c[i].num=0;
}
}
void fun(int l,int r)
{
if(l==r)
{

return;
}
int mid=(l+r)>>1;
fun(l,mid);
for(int i=l;i<=r;i++)
{
b[i]=a[i];
b[i].x=0;
}
sort(b+l,b+r+1,cmp);
for(int i=l;i<=r;i++)
{
if(b[i].id<=mid)
{
insert(b[i].z,dp[b[i].id]);
}
else
{
node temp=sum(b[i].z);
if(dp[b[i].id].len<temp.len+1)
{
dp[b[i].id].len=temp.len+1;
dp[b[i].id].num=temp.num;
}
else if(dp[b[i].id].len==temp.len+1)
dp[b[i].id].num+=temp.num;
}
}
for(int i=l;i<=r;i++)
{
if(b[i].id<=mid)
del(b[i].z);
}
fun(mid+1,r);

}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
e=0;
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
d[i]=a[i].z;

}

sort(a+1,a+n+1,cmp);
sort(d+1,d+1+n),e=unique(d+1,d+1+n)-d;

for(int i=1;i<=n;i++)
{
a[i].id=i;
dp[i].len=1;
dp[i].num=1;
a[i].z=lower_bound(d+1,d+1+e,a[i].z)-d;
c[i].len=0;
c[i].num=0;
}

fun(1,n);
node ans;
ans.len=0;
ans.num=0;
for(int i=1;i<=n;i++)
update(ans,dp[i]);
printf("%d %d\n",ans.len,ans.num%mod);
}
return 0;
}```

0 条评论

• ### HDU 5652 India and China Origins（并查集）

India and China Origins Time Limit: 2000/2000 MS (Java/Others)    Memory Limit:...

• ### ZOJ 3490 String Successor（模拟）

Time Limit: 2 Seconds Memory Limit: 65536 KB The successor to a string ca...

• ### 11-散列2 Hashing (25分)

The task of this problem is simple: insert a sequence of distinct positive integ...

• ### String Problem（KMP+最小表示法）- HDU 3374

Give you a string with length N, you can generate N strings by left shifts. For ...

• ### POJ 2311 Cutting Game(二维SG+Multi-Nim)

Description Urej loves to play various types of dull games. He usually asks oth...

• ### UVALive 6933 Virus synthesis（回文树）

The Head Elder of the tropical island of Lagrishan has a problem. A burst of ...

• ### HDU 3480 Division

Problem Description Little D is really interested in the theorem of sets recen...

• ### ZOJ 3537 Cake(凸包判定+区间DP)

Cake Time Limit: 1 Second Memory Limit: 32768 KB You want to hold a par...

### 活动推荐 