920C.md (1685B)
1 Source: https://codeforces.com/problemset/problem/920/C 2 3 C. Swap Adjacent Elements 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 standard input 16 17 output 18 19 standard output 20 21 You have an array *a* consisting of *n* integers. Each integer from 1 to *n* appears exactly once in this array. 22 23 For some indices *i* (1 ≤ *i* ≤ *n* - 1) it is possible to swap *i*-th element with (*i* + 1)-th, for other indices it is not possible. You may perform any number of swapping operations any order. There is no limit on the number of times you swap *i*-th element with (*i* + 1)-th (if the position is not forbidden). 24 25 Can you make this array sorted in ascending order performing some sequence of swapping operations? 26 27 Input 28 29 The first line contains one integer *n* (2 ≤ *n* ≤ 200000) — the number of elements in the array. 30 31 The second line contains *n* integers *a*1, *a*2, ..., *a**n* (1 ≤ *a**i* ≤ 200000) — the elements of the array. Each integer from 1 to *n* appears exactly once. 32 33 The third line contains a string of *n* - 1 characters, each character is either 0 or 1. If *i*-th character is 1, then you can swap *i*-th element with (*i* + 1)-th any number of times, otherwise it is forbidden to swap *i*-th element with (*i* + 1)-th. 34 35 Output 36 37 If it is possible to sort the array in ascending order using any sequence of swaps you are allowed to make, print YES. Otherwise, print NO. 38 39 Examples 40 41 Input 42 43 ``` 44 6 45 1 2 5 3 4 6 46 01110 47 ``` 48 49 Output 50 51 ``` 52 YES 53 ``` 54 55 Input 56 57 ``` 58 6 59 1 2 5 3 4 6 60 01010 61 ``` 62 63 Output 64 65 ``` 66 NO 67 ``` 68 69 Note 70 71 In the first example you may swap *a*3 and *a*4, and then swap *a*4 and *a*5.