codeforces-scrape

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

1485B.md (1617B)


      1 Source: https://codeforces.com/problemset/problem/1485/B
      2 
      3 B. Replace and Keep Sorted
      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 Given a positive integer $k$, two arrays are called $k$-similar if:
     22 
     23 * they are strictly increasing;
     24 * they have the same length;
     25 * all their elements are positive integers between $1$ and $k$ (inclusive);
     26 * they differ in exactly one position.
     27 
     28 You are given an integer $k$, a strictly increasing array $a$ and $q$ queries. For each query, you are given two integers $l_i \leq r_i$. Your task is to find how many arrays $b$ exist, such that $b$ is $k$-similar to array $[a_{l_i},a_{l_i+1}\ldots,a_{r_i}]$.
     29 
     30 Input
     31 
     32 The first line contains three integers $n$, $q$ and $k$ ($1\leq n, q \leq 10^5$, $n\leq k \leq 10^9$) — the length of array $a$, the number of queries and number $k$.
     33 
     34 The second line contains $n$ integers $a_1, a_2, \ldots,a_n$ ($1 \leq a_i \leq k$). This array is strictly increasing  — $a_1 \lt a_2 \lt \ldots \lt a_n$.
     35 
     36 Each of the following $q$ lines contains two integers $l_i$, $r_i$ ($1 \leq l_i \leq r_i \leq n$).
     37 
     38 Output
     39 
     40 Print $q$ lines. The $i$-th of them should contain the answer to the $i$-th query.
     41 
     42 Examples
     43 
     44 Input
     45 
     46 ```
     47 4 2 5
     48 1 2 4 5
     49 2 3
     50 3 4
     51 ```
     52 
     53 Output
     54 
     55 ```
     56 4
     57 3
     58 ```
     59 
     60 Input
     61 
     62 ```
     63 6 5 10
     64 2 4 6 7 8 9
     65 1 4
     66 1 2
     67 3 5
     68 1 6
     69 5 5
     70 ```
     71 
     72 Output
     73 
     74 ```
     75 8
     76 9
     77 7
     78 6
     79 9
     80 ```
     81 
     82 Note
     83 
     84 In the first example:
     85 
     86 In the first query there are $4$ arrays that are $5$-similar to $[2,4]$: $[1,4],[3,4],[2,3],[2,5]$.
     87 
     88 In the second query there are $3$ arrays that are $5$-similar to $[4,5]$: $[1,5],[2,5],[3,5]$.