Codeforces Round #835 (Div. 4) D. Challenging Valleys

Codeforces Round #835 (Div. 4) D. Challenging Valleys

One possible solution is to represent a range of equal element as a single element with that value. Construct this array $b$ and loop through it and check how many element bi satisfy the conditions $i=0$ or $b_{i-1}$< $b_i$ and $i=n-1$ or $bi$ > $bi+1$. If exactly one index satisfies these conditions, print “YES” and othewise “NO”.

Complexity: $O(n)$

#include
using namespace std;

int main()
{
    int T=1;cin>>T;
    while(T--)
    {
        int n;cin>>n;
        vector<int> a(n);
        for(int i=0;i<n;i++) cin>>a[i];

        n=unique(a.begin(),a.end())-a.begin();

        if(n==1)
        {
            cout<<"YES"<<endl;
            continue;
        }

        int res=0;
        if(a[0]<a[1]) res++;
        if(a[n-2]>a[n-1]) res++;

        for(int i=1;i<n-1;i++)
            if(a[i-1]>a[i] && a[i]<a[i+1])
                res++;

        if(res==1) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33