codeforces-scrape

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

811B.md (2621B)


      1 Source: https://codeforces.com/problemset/problem/811/B
      2 
      3 B. Vladik and Complicated Book
      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 Vladik had started reading a complicated book about algorithms containing *n* pages. To improve understanding of what is written, his friends advised him to read pages in some order given by permutation *P* = [*p*1, *p*2, ..., *p**n*], where *p**i* denotes the number of page that should be read *i*-th in turn.
     22 
     23 Sometimes Vladik’s mom sorted some subsegment of permutation *P* from position *l* to position *r* inclusive, because she loves the order. For every of such sorting Vladik knows number *x* — what index of page in permutation he should read. He is wondered if the page, which he will read after sorting, has changed. In other words, has *p**x* changed? After every sorting Vladik return permutation to initial state, so you can assume that each sorting is independent from each other.
     24 
     25 Input
     26 
     27 First line contains two space-separated integers *n*, *m* (1 ≤ *n*, *m* ≤ 104) — length of permutation and number of times Vladik's mom sorted some subsegment of the book.
     28 
     29 Second line contains *n* space-separated integers *p*1, *p*2, ..., *p**n* (1 ≤ *p**i* ≤ *n*) — permutation *P*. Note that elements in permutation are distinct.
     30 
     31 Each of the next *m* lines contains three space-separated integers *l**i*, *r**i*, *x**i* (1 ≤ *l**i* ≤ *x**i* ≤ *r**i* ≤ *n*) — left and right borders of sorted subsegment in *i*-th sorting and position that is interesting to Vladik.
     32 
     33 Output
     34 
     35 For each mom’s sorting on it’s own line print "Yes", if page which is interesting to Vladik hasn't changed, or "No" otherwise.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 5 5  
     43 5 4 3 2 1  
     44 1 5 3  
     45 1 3 1  
     46 2 4 3  
     47 4 4 4  
     48 2 5 3
     49 ```
     50 
     51 Output
     52 
     53 ```
     54 Yes  
     55 No  
     56 Yes  
     57 Yes  
     58 No
     59 ```
     60 
     61 Input
     62 
     63 ```
     64 6 5  
     65 1 4 3 2 5 6  
     66 2 4 3  
     67 1 6 2  
     68 4 5 4  
     69 1 3 3  
     70 2 6 3
     71 ```
     72 
     73 Output
     74 
     75 ```
     76 Yes  
     77 No  
     78 Yes  
     79 No  
     80 Yes
     81 ```
     82 
     83 Note
     84 
     85 Explanation of first test case:
     86 
     87 1. [1, 2, 3, 4, 5] — permutation after sorting, 3-rd element hasn’t changed, so answer is "Yes".
     88 2. [3, 4, 5, 2, 1] — permutation after sorting, 1-st element has changed, so answer is "No".
     89 3. [5, 2, 3, 4, 1] — permutation after sorting, 3-rd element hasn’t changed, so answer is "Yes".
     90 4. [5, 4, 3, 2, 1] — permutation after sorting, 4-th element hasn’t changed, so answer is "Yes".
     91 5. [5, 1, 2, 3, 4] — permutation after sorting, 3-rd element has changed, so answer is "No".