codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```