codeforces-scrape

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

1473D.md (2178B)


      1 Source: https://codeforces.com/problemset/problem/1473/D
      2 
      3 D. Program
      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 You are given a program that consists of $n$ instructions. Initially a single variable $x$ is assigned to $0$. Afterwards, the instructions are of two types:
     22 
     23 * increase $x$ by $1$;
     24 * decrease $x$ by $1$.
     25 
     26 You are given $m$ queries of the following format:
     27 
     28 * query $l$ $r$ — how many distinct values is $x$ assigned to if all the instructions between the $l$-th one and the $r$-th one inclusive are ignored and the rest are executed without changing the order?
     29 
     30 Input
     31 
     32 The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of testcases.
     33 
     34 Then the description of $t$ testcases follows.
     35 
     36 The first line of each testcase contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$) — the number of instructions in the program and the number of queries.
     37 
     38 The second line of each testcase contains a program — a string of $n$ characters: each character is either '+' or '-' — increment and decrement instruction, respectively.
     39 
     40 Each of the next $m$ lines contains two integers $l$ and $r$ ($1 \le l \le r \le n$) — the description of the query.
     41 
     42 The sum of $n$ over all testcases doesn't exceed $2 \cdot 10^5$. The sum of $m$ over all testcases doesn't exceed $2 \cdot 10^5$.
     43 
     44 Output
     45 
     46 For each testcase print $m$ integers — for each query $l$, $r$ print the number of distinct values variable $x$ is assigned to if all the instructions between the $l$-th one and the $r$-th one inclusive are ignored and the rest are executed without changing the order.
     47 
     48 Example
     49 
     50 Input
     51 
     52 ```
     53 2
     54 8 4
     55 -+--+--+
     56 1 8
     57 2 8
     58 2 5
     59 1 1
     60 4 10
     61 +-++
     62 1 1
     63 1 2
     64 2 2
     65 1 3
     66 2 3
     67 3 3
     68 1 4
     69 2 4
     70 3 4
     71 4 4
     72 ```
     73 
     74 Output
     75 
     76 ```
     77 1
     78 2
     79 4
     80 4
     81 3
     82 3
     83 4
     84 2
     85 3
     86 2
     87 1
     88 2
     89 2
     90 2
     91 ```
     92 
     93 Note
     94 
     95 The instructions that remain for each query of the first testcase are:
     96 
     97 1. empty program — $x$ was only equal to $0$;
     98 2. "-" — $x$ had values $0$ and $-1$;
     99 3. "---+" — $x$ had values $0$, $-1$, $-2$, $-3$, $-2$ — there are $4$ distinct values among them;
    100 4. "+--+--+" — the distinct values are $1$, $0$, $-1$, $-2$.