http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1485. Catch The Penguins 抓企鹅(张闻涛)
时间限制:2.0s   内存限制:512.0MB  
总提交次数:476   AC次数:93   平均分:51.24
将本题分享到:
   
 
问题描述
  Xyz带着他的教徒们乘着科考船一路破冰来到了南极大陆,发现这里有许许多多的企鹅。邪恶的Xyz想要抓很多企鹅回去开动物园,当宠物玩。但动物保护协会很快赶来,他必须尽快行动!
  我们把南极大陆看成一个三维直角坐标系。
  有N只企鹅,每只企鹅会在一定的时刻的出现,第i只企鹅在Ai时刻出现在坐标为(Bi,Ci,Di)的地方。
  Xyz要在某一时刻在某一地方(X,Y,Z)撒一张大网,将(0,0,0)到(X,Y,Z)这个大长方体里的企鹅全都网进去捕捉回家(还没出现的企鹅就不会被捉进去了)。
  为了快准狠而且保证不铺张浪费网,Xyz想知道不同时间不同地点撒网能抓到几个企鹅(这样的询问有Q个)。然后他再行动。
输入格式
  第一行一个整数N表示企鹅个数。
  第二行到N+1行每行四个实数(Ai,Bi,Ci,Di),表示企鹅的出现时间和位置
  第N+2行一个整数Q表示询问个数。
  接下来Q行每行四个实数(T,X,Y,Z),表示询问的时间和位置。
输出格式
  输出共Q行,每行一个整数,回答每个询问能抓到几个企鹅。
样例输入
1
0 0 0 0
2
1 1 1 1.0
1 1 1 -1
样例输出
1
0
数据规模和约定
  共20个数据
  数据1~3 N,Q<=1000
  数据4~6 N,Q<=5000
  数据7~10 N,Q<=10000
  数据11~14 N<=30000,Q<=10000
  数据15~18 N<=10000,Q<=30000
  数据19~20 N,Q<=30000