469B.md (2115B)
1 Source: https://codeforces.com/problemset/problem/469/B 2 3 B. Chat Online 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 Little X and Little Z are good friends. They always chat online. But both of them have schedules. 22 23 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*). 24 25 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? 26 27 Input 28 29 The first line contains four space-separated integers *p*, *q*, *l*, *r* (1 ≤ *p*, *q* ≤ 50; 0 ≤ *l* ≤ *r* ≤ 1000). 30 31 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). 32 33 It's guaranteed that *b**i* < *a**i* + 1 and *d**j* < *c**j* + 1 for all valid *i* and *j*. 34 35 Output 36 37 Output a single integer — the number of moments of time from the segment [*l*, *r*] which suit for online conversation. 38 39 Examples 40 41 Input 42 43 ``` 44 1 1 0 4 45 2 3 46 0 1 47 ``` 48 49 Output 50 51 ``` 52 3 53 ``` 54 55 Input 56 57 ``` 58 2 3 0 20 59 15 17 60 23 26 61 1 4 62 7 11 63 15 17 64 ``` 65 66 Output 67 68 ``` 69 20 70 ```