问题描述
Country A 与 B 是敌对国家，它们正在一场战争中互相发射导弹。
A 国共发射了 N N 枚导弹，其中第 i i 枚的发射时间为 Ta i Tai ，花费 Tac i Taci 的时间 飞到 B 国，并可对 B 国造成 Da i Dai 点损害。
B 国共发射了 M M 枚导弹，其中第 i i 枚的发射时间为 Tb i Tbi ，花费 Tbc i Tbci 的时间 飞到 A 国，并可对 A 国造成 Db i Dbi 点伤害。
不过，两国都有一套导弹防御系统，A 国的导弹防御系统可以在某个连续 TA TA 的时间段内开启（其它时间关闭），B 国的导弹系统可以在某个连续 TB TB 的时 间段内开启（其它时间关闭）。当拦截系统开启时，所有到达该国的导弹会立即 调转方向按照原本的速度飞向对面国家；当拦截系统关闭时，导弹会对该国造成 损害（拦截系统在时间段端点处，即恰好开启和关闭时也被认为是开启的）。
现在 A 国的情报部门探听到 B 国将于时刻 X X 开启导弹系统（在时刻 X+TB X+TB 关闭）。作为 A 国的总统，请你决定何时开启本国的导弹系统，可以使受到的损害最小。
输入格式
每个测试点包含多组数据（不超过 50 组），对于每组数据：
第一行两个整数 TA TA , TB TB ，
第二行一个整数 X X ，
第三行两个整数 N N , M M 。
接下来 N N 行每行三个整数 Ta i Tai ，Tac i Taci ，Da i Dai 。
接下来 M M 行每行三个整数 Tb i Tbi ，Tbc i Tbci ，Db i Dbi 。
输出格式
对于每组数据，输出 A 国受到的最小损害。
样例输入
2 2 2 1 0 1 1 10 4 5 3 2 2 1 2 10 1 5 7 1 3 2 0 4 8
输出格式
017
据规模与约定
对于 20%的数据，0<=N,M<=100 0<=N,M<=100 。
对于另外 20%的数据，TA=0 TA=0 。
对于另外 20%的数据，TB=0 TB=0 。
对于 100%的数据，0<=TA,TB,X,Ta i ,Tac i ,Tb i ,Tbc i <=10 8 ，0<=N,M<=10 4 ，1<=Da i ,Db i <=10 4 0<=TA,TB,X,Tai,Taci,Tbi,Tbci<=108，0<=N,M<=104，1<=Dai,Dbi<=104 。
时空限制
1S/512MB
题解
预处理A和B的导弹，看哪些可以被反弹，求出欲反弹导弹需要覆盖哪些地区，然后排序，枚举，优先队列。
1 #include2 using namespace std; 3 const int maxn=10100; 4 long long ta,tb,x,tot,n,m,sum,ans; 5 long long read(){ 6 long long lin = 0; 7 char x= getchar(); 8 while(x<'0' || x > '9'){ 9 x = getchar();10 }11 while(x >= '0' && x <= '9'){12 lin = (lin << 1) + (lin << 3) + x - '0';13 x = getchar();14 }15 return lin;16 }17 struct st{18 long long st,en,tim,att;19 }a[maxn << 1],s[maxn << 1];20 bool com(st a,st b){21 return a.en < b.en;22 }23 void putin(){24 for(long long i=1;i<=n;i++){25 a[i].st = read();26 a[i].tim = read();27 a[i].att = read();28 a[i].en = 0;29 if(a[i].st + a[i].tim >= x && a[i].st + a[i].tim <= x + tb){30 sum += a[i].att;31 tot++;32 s[tot] = a[i];33 long long k = (x + tb - a[i].st - a[i].tim) % (a[i].tim << 1);34 s[tot].en = x + tb - k + a[i].tim;35 s[tot].st += s[tot].tim << 1;36 }37 }38 for(long long i=1;i<=m;i++){39 a[i].st = read();40 a[i].tim = read();41 a[i].att = read();42 a[i].en = 0;43 tot++;44 sum += a[i].att;45 s[tot] = a[i];46 long long k = (x + tb - a[i].st) % (a[i].tim << 1);47 s[tot].en = x + tb - k + a[i].tim;48 s[tot].st += s[tot].tim;49 if(s[tot].st + s[tot].tim < x || s[tot].st + s[tot].tim > x + tb){50 s[tot].en = s[tot].st;51 }52 } 53 }54 bool operator <(st a,st b){55 return a.st > b.st;56 }57 int main(){58 while(cin>>ta>>tb){59 sum = 0;60 tot = 0;61 x = read();62 n = read();63 m = read();64 putin();65 sort(s+1,s+1+tot,com);66 ans = sum;67 priority_queue q;68 for(long long i=1;i<=tot;i++){69 q.push(s[i]);70 sum -= s[i].att;71 while(q.top().st < s[i].en - ta && !q.empty()){72 sum += q.top().att;73 q.pop();74 }75 ans = min(ans,sum);76 }77 cout< <