CF 279C - Ladder

 1  /*
 2  Problem link
 3  Type: Binary Search
 4  Algorithm:
 5      Let s[i] store the index j in the array where a[j]<a[j-1].
 6      Let t[i] store the index j in the array where a[j]>a[j-1].
 7      Ex: a: 1 2 1 3 3 5 2 1 (a[0] = 0)
 8      ->  s: 3 7 8
 9      ->  t: 2 4 6
10      For each question with l,r, find in s the smallest element
11      that pos0 = k for l+1<=s[k]<=r.
12      If we cant find pos0 then s[l..r] is non-decreasing hence
13      the answer is "Yes". Else if we can find pos0, search for
14      the smallest element in t that pos1 = k for pos0+1<=t[k]<=r.
15      If we cant find any pos1, then s[pos0+1..r] is non-increasing
16      the the answer is "Yes" otherwise the answer is "No".
17  */
18  #include <iostream>
19  #include <cstdio>
20  #include <cstring>
21  #include <cmath>
22  #include <cstdlib>
23  
24  using namespace std;
25  const int maxn = 100010;
26  
27  int a[maxn], s[maxn], t[maxn];
28  int n,q,m,k;
29  
30  int BSearchDec(int left, int right);
31  int BSearchInc(int left, int right);
32  
33  int main()
34  {
35      cin >> n >> q;
36      a[0] = 0; m = 0; k = 0;
37      for (int i=1; i<=n; i++)
38      {
39          cin >> a[i];
40          if (a[i]<a[i-1]) s[++m] = i;
41          else if (a[i]>a[i-1]) t[++k] = i;
42      }
43      for (int i=1; i<=q; i++)
44      {
45          int l,r,pos0,pos1;
46          cin >> l >> r;
47          pos0 = BSearchDec(l+1,r);
48          if (pos0==-1) cout << "Yes" << endl;
49          else
50          {
51              pos1 = BSearchInc(pos0+1,r);
52              if (pos1==-1) cout << "Yes" << endl;
53              else cout << "No" << endl;
54          }
55      }
56      return 0;
57  }
58  
59  int BSearchDec(int left, int right)
60  {
61      if (left>right) return(-1);
62      int l,r,mid;
63      l = 1; r = m;
64      do
65      {
66          mid = (l+r)/2;
67          if (s[mid]>=left && s[mid]<=right) r = mid;
68          else if (s[mid]<left) l = mid;
69          else r = mid;
70      } while (l+1<r);
71      if (s[l]>=left && s[l]<=right) return s[l];
72      else if (s[r]>=left && s[r]<=right) return s[r];
73      else return(-1);
74  }
75  
76  int BSearchInc(int left, int right)
77  {
78      if (left>right) return(-1);
79      int l,r,mid;
80      l = 1; r = k;
81      do
82      {
83          mid = (l+r)/2;
84          if (t[mid]>=left && t[mid]<=right) r = mid;
85          else if (t[mid]<left) l = mid;
86          else r = mid;
87      } while (l+1<r);
88      if (t[l]>=left && t[l]<=right) return t[l];
89      else if (t[r]>=left && t[r]<=right) return t[r];
90      else return(-1);
91  }