记录编号	136073	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]电子对撞机	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	5.651 s
提交时间	2014-11-02 11:35:18	内存使用	99.50 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int SIZEN=2000010;
class ELECTRON{
public:
	int x,p,e;
}ele[SIZEN];
bool operator < (ELECTRON a,ELECTRON b){
	return a.x<b.x;
}
int x[SIZEN];//电子的"实际位置"
int N,M,L,T;
int rl[SIZEN],rr[SIZEN];//接收器
LL s[SIZEN],ts[SIZEN];//s存了每个长度2L的整轮,ts存了后面的余数,一开始是储存差分的
void addseg(LL s[],int l,int r,int c){
	if(l>r||l>=N||r<0) return;
	s[max(l,1)]+=c;
	if(r+1<N) s[r+1]-=c;
}
void calc_real(LL s[]){
	s[0]=0;
	for(int i=1;i<N;i++) s[i]+=s[i-1];
}
int ta,tb;//时间限制下的左右区间
int ra[SIZEN],rb[SIZEN];//接收器限制下的左右区间
int event[SIZEN];
int E[3]={1,4,25};
void work(void){
	int round=T/(2*L);
	T%=(2*L);
	int T1=T;
	for(int i=0;i==0;i++){//试图优美的丑陋写法......
		/*t的意义是卡住"0<=跨立时间<=T1"的一段
		a,b跨立k的时间(a<b):1/2(k-x[a]-x[b]),这里我们取k=2*L
		此时2*跨立时间=4L-x[a]-x[b]
		可见随着b增加,跨立时间递减*/
		tb=N*2-1;
		while(4*L-x[tb]-x[i]<0) tb--;
		if(2*T<=4*L-x[i])	T1=T,ta=tb;
		else T1=T-2*L,ta=2*N-1;
		while(ta>0&&4*L-x[ta-1]-x[i]<=2*T1) ta--;
		for(int j=0;j<M;j++){
			ra[j]=i;
			while(x[ra[j]]-x[i]<2*rl[j]) ra[j]++;
			rb[j]=i;
			while(rb[j]+1<i+N&&x[rb[j]+1]-x[i]<=2*rr[j]) rb[j]++;
			if(T1==T)
				addseg(ts,max(ta,ra[j])-i,min(tb,rb[j])-i,1);
			else{
				addseg(ts,ra[j]-i,min(tb,rb[j])-i,1);
				addseg(ts,max(ta,ra[j])-i,rb[j]-i,1);
			}
			addseg(s,ra[j]-i,rb[j]-i,1);
		}
	}
	for(int i=1;i<N;i++){
		//这时,跨立时间整体减少,图像向下平移
		while(4*L-x[tb]-x[i]<0) tb--;
		if(T1==T&&2*T>4*L-x[i]) T1=T-2*L,ta=2*N-1;
		while(ta>0&&4*L-x[ta-1]-x[i]<=2*T1) ta--;
		for(int j=0;j<M;j++){
			while(x[ra[j]]-x[i]<2*rl[j]) ra[j]++;
			while(rb[j]+1<i+N&&x[rb[j]+1]-x[i]<=2*rr[j]) rb[j]++;
			if(T1==T)
				addseg(ts,max(ta,ra[j])-i,min(tb,rb[j])-i,1);
			else{
				addseg(ts,ra[j]-i,min(tb,rb[j])-i,1);
				addseg(ts,max(ta,ra[j])-i,rb[j]-i,1);
			}
			addseg(s,ra[j]-i,rb[j]-i,1);
		}
	}
	calc_real(s);
	calc_real(ts);
	LL ans=0;
	for(int i=1;i<N;i++){
		LL k=E[ele[i-1].e+ele[i].e];
		LL tim=s[i]*round+ts[i];
		ans+=k*tim;
	}
	printf("%lld\n",ans);
}
void read(void){
	scanf("%d%d%d%d",&N,&M,&L,&T);
	for(int i=0;i<N;i++){
		scanf("%d%d%d",&ele[i].x,&ele[i].p,&ele[i].e);
		if(ele[i].p==1) x[i]=ele[i].x;//向右
		else x[i]=2*L-ele[i].x;//向左
	}
	for(int i=0;i<M;i++) scanf("%d%d",&rl[i],&rr[i]);
	sort(ele,ele+N);
	sort(x,x+N);
	for(int i=0;i<N;i++) x[i+N]=x[i]+2*L;
}
int main(){
	freopen("nt2012_energy.in","r",stdin);
	freopen("nt2012_energy.out","w",stdout);
	read();
	work();
	return 0;
}