{"problem":{"name":"C. Swap Adjacent Elements","description":{"content":"You have an array _a_ consisting of _n_ integers. Each integer from 1 to _n_ appears exactly once in this array. For some indices _i_ (1 ≤ _i_ ≤ _n_ - 1) it is possible to swap _i_\\-th element with (","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF920C"},"statements":[{"statement_type":"Markdown","content":"You have an array _a_ consisting of _n_ integers. Each integer from 1 to _n_ appears exactly once in this array.\n\nFor 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).\n\nCan you make this array sorted in ascending order performing some sequence of swapping operations?\n\n## Input\n\nThe first line contains one integer _n_ (2 ≤ _n_ ≤ 200000) — the number of elements in the array.\n\nThe 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.\n\nThe 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.\n\n## Output\n\nIf 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_.\n\n[samples]\n\n## Note\n\nIn the first example you may swap _a_3 and _a_4, and then swap _a_4 and _a_5.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"你有一个包含 $n$ 个整数的数组 $[a]$。数组中的每个整数从 $1$ 到 $n$ 恰好出现一次。\n\n对于某些索引 $i$（$1 ≤ i ≤ n - 1$），你可以交换第 $i$ 个元素与第 $(i + 1)$ 个元素；而对于其他索引，这种交换是不允许的。你可以执行任意次数的交换操作，且顺序任意。对于非禁止的位置，你可以任意多次交换第 $i$ 个元素与第 $(i + 1)$ 个元素。\n\n你能否通过执行某些交换操作序列，使该数组按升序排列？\n\n第一行包含一个整数 $n$（$2 ≤ n ≤ 200000$）——数组中元素的个数。\n\n第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$1 ≤ a_i ≤ 200000$）——数组的元素。每个从 $1$ 到 $n$ 的整数恰好出现一次。\n\n第三行包含一个长度为 $n - 1$ 的字符串，每个字符为 _0_ 或 _1_。如果第 $i$ 个字符是 _1_，则你可以任意多次交换第 $i$ 个元素与第 $(i + 1)$ 个元素；否则，这种交换是被禁止的。\n\n如果你可以通过允许的交换操作序列将数组排序为升序，请输出 _YES_；否则，输出 _NO_。\n\n在第一个示例中，你可以交换 $a_3$ 和 $a_4$，然后交换 $a_4$ 和 $a_5$。\n\n## Input\n\n第一行包含一个整数 $n$（$2 ≤ n ≤ 200000$）——数组中元素的个数。第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$1 ≤ a_i ≤ 200000$）——数组的元素。每个从 $1$ 到 $n$ 的整数恰好出现一次。第三行包含一个长度为 $n - 1$ 的字符串，每个字符为 _0_ 或 _1_。如果第 $i$ 个字符是 _1_，则你可以任意多次交换第 $i$ 个元素与第 $(i + 1)$ 个元素；否则，这种交换是被禁止的。\n\n## Output\n\n如果你可以通过允许的交换操作序列将数组排序为升序，请输出 _YES_；否则，输出 _NO_。\n\n[samples]\n\n## Note\n\n在第一个示例中，你可以交换 $a_3$ 和 $a_4$，然后交换 $a_4$ 和 $a_5$。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the length of the array.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a permutation of $ \\{1, 2, \\dots, n\\} $.  \nLet $ S \\in \\{0,1\\}^{n-1} $ be a binary string where $ S[i] = 1 $ indicates that swapping $ a_i $ and $ a_{i+1} $ is permitted, for $ i \\in \\{1, \\dots, n-1\\} $.\n\n**Constraints**  \n1. $ 2 \\leq n \\leq 200000 $  \n2. $ A $ is a permutation of $ \\{1, 2, \\dots, n\\} $  \n3. $ S[i] \\in \\{0,1\\} $ for all $ i \\in \\{1, \\dots, n-1\\} $\n\n**Objective**  \nDetermine whether $ A $ can be sorted into ascending order $ (1, 2, \\dots, n) $ using any number of adjacent swaps, where swaps at position $ i $ are allowed if and only if $ S[i] = 1 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF920C","tags":["dfs and similar","greedy","math","sortings","two pointers"],"sample_group":[["6\n1 2 5 3 4 6\n01110","YES"],["6\n1 2 5 3 4 6\n01010","NO"]],"created_at":"2026-03-03 11:00:39"}}