A9605. Chat Online
编程题
普及/提高-
知识点
题目描述
Little X and Little Z are good friends. They always chat online. But both of them have schedules.
Little Z has fixed schedule. He always online at any moment of time between $a_{1}$ and $b_{1}$ , between $a_{2}$ and $b_{2}$ , ..., between $a_{p}$ and $b_{p}$ (all borders inclusive). But the schedule of Little X is quite strange, it depends on the time when he gets up. If he gets up at time $0$ , he will be online at any moment of time between $c_{1}$ and $d_{1}$ , between $c_{2}$ and $d_{2}$ , ..., between $c_{q}$ and $d_{q}$ (all borders inclusive). But if he gets up at time $t$ , these segments will be shifted by $t$ . They become $[c_{i}+t,d_{i}+t]$ (for all $i$ ).
If at a moment of time, both Little X and Little Z are online simultaneosly, they can chat online happily. You know that Little X can get up at an integer moment of time between $l$ and $r$ (both borders inclusive). Also you know that Little X wants to get up at the moment of time, that is suitable for chatting with Little Z (they must have at least one common moment of time in schedules). How many integer moments of time from the segment $[l,r]$ suit for that?
Little Z has fixed schedule. He always online at any moment of time between $a_{1}$ and $b_{1}$ , between $a_{2}$ and $b_{2}$ , ..., between $a_{p}$ and $b_{p}$ (all borders inclusive). But the schedule of Little X is quite strange, it depends on the time when he gets up. If he gets up at time $0$ , he will be online at any moment of time between $c_{1}$ and $d_{1}$ , between $c_{2}$ and $d_{2}$ , ..., between $c_{q}$ and $d_{q}$ (all borders inclusive). But if he gets up at time $t$ , these segments will be shifted by $t$ . They become $[c_{i}+t,d_{i}+t]$ (for all $i$ ).
If at a moment of time, both Little X and Little Z are online simultaneosly, they can chat online happily. You know that Little X can get up at an integer moment of time between $l$ and $r$ (both borders inclusive). Also you know that Little X wants to get up at the moment of time, that is suitable for chatting with Little Z (they must have at least one common moment of time in schedules). How many integer moments of time from the segment $[l,r]$ suit for that?
输入格式
The first line contains four space-separated integers $p,q,l,r$ ( $1<=p,q<=50; 0<=l<=r<=1000$ ).
Each of the next $p$ lines contains two space-separated integers $a_{i},b_{i}$ ( $0<=a_{i}<b_{i}<=1000$ ). Each of the next $q$ lines contains two space-separated integers $c_{j},d_{j}$ ( $0<=c_{j}<d_{j}<=1000$ ).
It's guaranteed that $b_{i}<a_{i+1}$ and $d_{j}<c_{j+1}$ for all valid $i$ and $j$ .
Each of the next $p$ lines contains two space-separated integers $a_{i},b_{i}$ ( $0<=a_{i}<b_{i}<=1000$ ). Each of the next $q$ lines contains two space-separated integers $c_{j},d_{j}$ ( $0<=c_{j}<d_{j}<=1000$ ).
It's guaranteed that $b_{i}<a_{i+1}$ and $d_{j}<c_{j+1}$ for all valid $i$ and $j$ .
输出格式
Output a single integer — the number of moments of time from the segment $[l,r]$ which suit for online conversation.
输入输出样例
输入 #1
1 1 0 4 2 3 0 1
输出 #1
3
输入 #2
2 3 0 20 15 17 23 26 1 4 7 11 15 17
输出 #2
20