http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1332. 电子对撞机(刘洪轩)
时间限制:3.0s   内存限制:256.0MB  
总提交次数:98   AC次数:32   平均分:49.18
将本题分享到:
   
 
【题意描述】
  感谢HQ提供题目描述
  Q国最近科学技术不断进步,经过不懈努力,Q国主席QQ终于在质子对撞机的基础上研发了新一代能量供给装置:电子对撞机。
  这个设备呈长条状且对外封闭,设备内部有N个带有一定能量的电子。长条状的外形使得这些电子只能沿条形走向左右运动。设备长度为L,左端位置为0,右端位置为L。内部的电子速率恒定,每一个单位时间在左右方向上移动一个单位长度,而方向可能是向左或向右。当两个电子相遇即运动到同一个点时,它们之间会发生对撞,对撞后它们的速率不变但运动方向反向。设备的两个端点处(即坐标为0和L的位置)存在保护外壳,当电子运动到端点时会和外壳发生碰撞,碰撞后电子也会保持不变的速率但运动方向反向。电子分为高能电子和低能电子,电子之间对撞会产生能量,低能电子和低能电子对撞会产生1个单位的能量,低能电子和高能电子对撞会产生4个单位的能量,高能电子和高能电子对撞会产生25个单位的能量,电子和外壳碰撞不会产生能量。设备内部还有M个能量接收器,每个接收器可以接受从A到B的一个区间内(包括两个端点)的能量,且接收器可以接受的范围没有交集。若电子对撞的位置处于接收器的接受范围内,对撞产生的能量会被接收器接受,若对撞位置不在接收器上,这些能量则会丢失。这项技术的核心在于:对撞时电子的能量不会有损失,所以电子对撞机可以一直不断地运行下去供给能量。
  现在QQ已经制造出了第一批电子对撞机,并测得了时刻为0时电子的位置和运动状态,现在QQ想知道从时刻0到时刻T(包括T)总共接收到的能量,于是这个任务交给了神犇你。
【输入格式】
  第一行四个整数 N, M, L, T,分别表示电子个数,能量接收器个数,设备长度和时间。
  之后N行每行3个整数,Xi, Pi, Ei分别表示第i个电子的位置,运动方向和能量级别。
  Pi为1表示向右运动,为-1表示向左运动。
  Ei为0表示低能电子,为1表示高能电子。
  之后M行每行2个整数,Ai和 Bi,表示接收器的接收范围。
【输出格式】
  仅一行,包括一个整数,表示总共接收到的能量数。
【样例输入】
  3 1 8 7
  2 1 0
  4 -1 0
  7 1 1
  3 6
【样例输出】
  5
【样例说明】
  T=1时,在位置3,第一个电子和第二个电子对撞,产生1的能量。
  在位置8,第三个电子和右侧外壳碰撞。
  T=3.5时,在位置5.5,第二个电子和第三个电子对撞,产生4的能量。
  T=4时,在位置0,第一个电子和左侧外壳碰撞。
  T=6时,在位置8,第三个电子和右侧外壳碰撞。
  T=6.5时,在位置2.5,第一个电子和第二个电子对撞,产生1的能量,由于在接收器范围外,能量丢失。
  最后结果为1+4=5个单位能量。
【数据规模和约定】
  输入保证开始时任意两个电子不处于同一个位置。
  输入保证接收器的接受范围没有交集,且所有接收器按坐标从小到大的顺序给出。
  共20组数据,满足如下条件

1 ~ 2
N <= 10
M <= 3
L <= 1000,
T <= 100000
2 <= N <= 1000000,
1 <= M <= 10,
2 <= L <= 100000000,
0 <= T <= 1000000000,
0 < X < L
0 <= A < B <= L

3 ~ 4
N <= 100
Ei = 0
L <= 1000000
5 ~ 6
N <= 1000

7 ~ 8
M = 1 且
A1 = 0, B1 = L
9 ~ 10
N <= 100000
11~12

13~20