Ladder (Codeforces 279C)
Tags: Implement, two pointers

You've got an array, consisting of n integers a1, a2, ..., an. Also, you've got m queries, the i-th query is described by two integers li, ri. Numbers li, ri define a subsegment of the original array, that is, the sequence of numbers ali, ali + 1, ali + 2, ..., ari. For each query you should check whether the corresponding segment is a ladder. A ladder is a sequence of integers b1, b2, ..., bk, such that it first doesn't decrease, then doesn't increase. In other words, there is such integer x (1 ≤ x ≤ k), that the following inequation fulfills: b1 ≤ b2 ≤ ... ≤ bx ≥ bx + 1 ≥ bx + 2... ≥ bk. Note that the non-decreasing and the non-increasing sequences are also considered ladders.

Input: The first line contains two integers n and m (1 ≤ n, m ≤ 105) — the number of array elements and the number of queries. The second line contains the sequence of integers a1, a2, ..., an (1 ≤ ai ≤ 109), where number ai stands for the i-th array element.The following m lines contain the description of the queries. The i-th line contains the description of the i-th query, consisting of two integers li, ri (1 ≤ li ≤ ri ≤ n) — the boundaries of the subsegment of the initial array.The numbers in the lines are separated by single spaces.

Output: Print m lines, in the i-th line print word "Yes" (without the quotes), if the subsegment that corresponds to the i-th query is the ladder, or word "No" (without the quotes) otherwise. 


Sample Inputs:
8 6
1 2 1 3 3 5 2 1
1 3
2 3
2 4
8 8
1 4
5 8

Sample Outputs:
Yes
Yes
No
Yes
No
Yes

Solution (Python):
import sys
input = sys.stdin.readline

def inp():
    return int(input())

def inlt():
    return list(map(int, input().split()))

def insr():
    s = input()
    return list(s[:len(s) - 1])

def invr():
    return map(int, input().split())

def Ladder():
    (n, m) = invr()
    sequence = inlt()
    increasing_till_after_index = []
    increasing_till_before_index = []
    ptr1 = 0
    ptr2 = 0
    while ptr1 <= n - 1:
        if ptr2 < ptr1:
            ptr2 = ptr1
        while ptr2 <= n - 2 and sequence[ptr2 + 1] >= sequence[ptr2]:
            ptr2 += 1
        increasing_till_after_index.append(ptr2)
        ptr1 += 1
    ptr1 = n - 1
    ptr2 = n - 1
    while ptr1 >= 0:
        if ptr2 > ptr1:
            ptr2 = ptr1
        while ptr2 >= 1 and sequence[ptr2 - 1] >= sequence[ptr2]:
            ptr2 -= 1
        increasing_till_before_index.append(ptr2)
        ptr1 -= 1
    increasing_till_before_index.reverse()
    outputStr = ''
    for i in range(m):
        (l, r) = invr()
        if increasing_till_after_index[l - 1] >= increasing_till_before_index[r - 1]:
            outputStr += 'Yes' + '\n'
        else:
            outputStr += 'No' + '\n'
    outputStr = outputStr.strip()
    print(outputStr)
    return
Ladder()

Solution (Python):
import sys, threading, os, io
import math
import time
from os import path
from collections import defaultdict, Counter, deque
from bisect import *
from string import ascii_lowercase
from functools import cmp_to_key
import heapq
from bisect import bisect_left as lower_bound
from bisect import bisect_right as upper_bound
from io import BytesIO, IOBase

def lcm(a, b):
    return a * b // math.gcd(a, b)
input = lambda : sys.stdin.readline().rstrip()

def lmii():
    return list(map(int, input().split()))

def ii():
    return int(input())

def si():
    return str(input())

def lmsi():
    return list(map(str, input().split()))

def mii():
    return map(int, input().split())

def msi():
    return map(str, input().split())
i2c = lambda n: chr(ord('a') + n)
c2i = lambda c: ord(c) - ord('a')
if os.path.exists('/Users/nitishkumar/Documents/Template_Codes/Python/CP/Codeforces/input.txt'):
    sys.stdin = open('/Users/nitishkumar/Documents/Template_Codes/Python/CP/Codeforces/input.txt', 'r')
    sys.stdout = open('/Users/nitishkumar/Documents/Template_Codes/Python/CP/Codeforces/output.txt', 'w')
else:
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def solve():
    (n, q) = mii()
    a = lmii()
    non_inc = [i for i in range(n)]
    non_dec = [i for i in range(n)]
    for i in range(1, n):
        if a[i] <= a[i - 1]:
            non_inc[i] = non_inc[i - 1]
    for i in range(n - 2, -1, -1):
        if a[i] <= a[i + 1]:
            non_dec[i] = non_dec[i + 1]
    for _ in range(q):
        (l, r) = lmii()
        if non_inc[r - 1] - non_dec[l - 1] <= 0:
            print('Yes')
        else:
            print('No')
solve()

Solution (Python):
""""""
import sys
import heapq
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
print = sys.stdout.write
sys.setrecursionlimit(100000)

def PRINT(lst, sep=' '):
    print(sep.join(map(str, lst)))
I = lambda : list(map(int, input().split(' ')))

def solve(lst, queries):
    n = len(lst)
    arr_f = [1]
    cur_max = 1
    for i in range(n - 2, -1, -1):
        if lst[i] <= lst[i + 1]:
            cur_max += 1
        else:
            cur_max = 1
        arr_f.append(cur_max)
    arr_f.reverse()
    arr_b = [1]
    cur_max = 1
    for i in range(n - 1):
        if lst[i + 1] <= lst[i]:
            cur_max += 1
        else:
            cur_max = 1
        arr_b.append(cur_max)
    ans = []
    for (l, r) in queries:
        l = l - 1
        r = r - 1
        if arr_f[l] + arr_b[r] >= r - l + 1:
            ans.append('Yes')
        else:
            ans.append('No')
    PRINT(ans, sep='\n')
(n, m) = I()
lst = I()
queries = [I() for i in range(m)]
solve(lst, queries)