codeforces-scrape

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

1358C.md (2321B)


      1 Source: https://codeforces.com/problemset/problem/1358/C
      2 
      3 C. Celex Update
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 During the quarantine, Sicromoft has more free time to create the new functions in "Celex-2021". The developers made a new function GAZ-GIZ, which infinitely fills an infinite table to the right and down from the upper left corner as follows:
     22 
     23  ![](https://espresso.codeforces.com/50d992c26f376f2bde3505ba72d122b46ccc6688.png)  The cell with coordinates $(x, y)$ is at the intersection of $x$-th row and $y$-th column. Upper left cell $(1,1)$ contains an integer $1$.
     24 
     25 The developers of the SUM function don't sleep either. Because of the boredom, they teamed up with the developers of the RAND function, so they added the ability to calculate the sum on an arbitrary path from one cell to another, moving down or right. Formally, from the cell $(x,y)$ in one step you can move to the cell $(x+1, y)$ or $(x, y+1)$.
     26 
     27 After another Dinwows update, Levian started to study "Celex-2021" (because he wants to be an accountant!). After filling in the table with the GAZ-GIZ function, he asked you to calculate the quantity of possible different amounts on the path from a given cell $(x_1, y_1)$ to another given cell $(x_2, y_2$), if you can only move one cell down or right.
     28 
     29 Formally, consider all the paths from the cell $(x_1, y_1)$ to cell $(x_2, y_2)$ such that each next cell in the path is located either to the down or to the right of the previous one. Calculate the number of different sums of elements for all such paths.
     30 
     31 Input
     32 
     33 The first line contains one integer $t$ ($1 \le t \le 57179$) — the number of test cases.
     34 
     35 Each of the following $t$ lines contains four natural numbers $x_1$, $y_1$, $x_2$, $y_2$ ($1 \le x_1 \le x_2 \le 10^9$, $1 \le y_1 \le y_2 \le 10^9$) — coordinates of the start and the end cells.
     36 
     37 Output
     38 
     39 For each test case, in a separate line, print the number of possible different sums on the way from the start cell to the end cell.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 4
     47 1 1 2 2
     48 1 2 2 4
     49 179 1 179 100000
     50 5 7 5 7
     51 ```
     52 
     53 Output
     54 
     55 ```
     56 2
     57 3
     58 1
     59 1
     60 ```
     61 
     62 Note
     63 
     64 In the first test case there are two possible sums: $1+2+5=8$ and $1+3+5=9$. ![](https://espresso.codeforces.com/54f16af83cc4838bce87a408843f620cc45d5ee1.png)