codeforces-scrape

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

1861C.md (3199B)


      1 Source: https://codeforces.com/problemset/problem/1861/C
      2 
      3 C. Queries for the Array
      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 Monocarp had an array $a$ consisting of integers. Initially, this array was empty.
     22 
     23 Monocarp performed three types of queries to this array:
     24 
     25 * choose an integer and append it to the end of the array. Each time Monocarp performed a query of this type, he wrote out a character +;
     26 * remove the last element from the array. Each time Monocarp performed a query of this type, he wrote out a character -. Monocarp never performed this query on an empty array;
     27 * check if the array is sorted in non-descending order, i.,e. $a_1 \le a_2 \le \dots \le a_k$, where $k$ is the number of elements in the array currently. Every array with less than $2$ elements is considered sorted. If the array was sorted by the time Monocarp was performing that query, he wrote out a character 1. Otherwise, he wrote out a character 0.
     28 
     29 You are given a sequence $s$ of $q$ characters 0, 1, + and/or -. These are the characters that were written out by Monocarp, given in the exact order he wrote them out.
     30 
     31 You have to check if this sequence is consistent, i. e. it was possible for Monocarp to perform the queries so that the sequence of characters he wrote out is exactly $s$.
     32 
     33 Input
     34 
     35 The first line of the input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     36 
     37 Each test case consists of one line containing the string $s$ ($1 \le |s| \le 2 \cdot 10^5$). This string consists of characters 0, 1, + and/or -. This is the sequence of characters written by Monocarp, in the order he wrote them.
     38 
     39 Additional constraints on the input:
     40 
     41 * for every prefix of $s$, the number of characters + on it is not less than the number of characters - on it. In other words, if Monocarp actually performed these queries, he would never try to remove the last element from the empty array;
     42 * the sum of $|s|$ over all test cases does not exceed $2 \cdot 10^5$.
     43 
     44 Output
     45 
     46 For each test case, print YES if it was possible for Monocarp to perform the queries so that the sequence of characters he wrote is exactly $s$. Otherwise, print NO.
     47 
     48 You can print each letter in any register.
     49 
     50 Example
     51 
     52 Input
     53 
     54 ```
     55 7
     56 
     57 ++1
     58 
     59 +++1--0
     60 
     61 +0
     62 
     63 0
     64 
     65 ++0-+1-+0
     66 
     67 ++0+-1+-0
     68 
     69 +1-+0
     70 ```
     71 
     72 Output
     73 
     74 ```
     75 YES
     76 NO
     77 NO
     78 NO
     79 YES
     80 NO
     81 NO
     82 ```
     83 
     84 Note
     85 
     86 In the first test case, Monocarp could perform the following sequence of queries:
     87 
     88 * add the integer $13$;
     89 * add the integer $37$;
     90 * check that the current array $[13, 37]$ is sorted in non-descending order (and it is sorted).
     91 
     92 In the fifth test case, Monocarp could perform the following sequence of queries:
     93 
     94 * add the integer $3$;
     95 * add the integer $2$;
     96 * check that the current array $[3, 2]$ is sorted (it is not);
     97 * remove the last element;
     98 * add the integer $3$;
     99 * check that the current array $[3, 3]$ is sorted (it is);
    100 * remove the last element;
    101 * add the integer $-5$;
    102 * check that the current array $[3, -5]$ is sorted (it is not).
    103 
    104 In all other test cases of the example test, it is impossible for Monocarp to write the sequence $s$ when performing the queries according to the statement.