Codeforces Round #616 (Div. 2) - Codeforces Round #616 (Div. 2)

http://codeforces.com/contest/1291/problem/B

Problem - B - Codeforces

문제

strictly increasing or strictly decreasing array is sharpened

입력으로 들어오는 배열의 요소가 증가 하거나, 감소한다면 날카롭다고 한다.

또한 증가하다가 감소하는 ㅅ 모양도 날카롭다고 한다.

주어지는 N 개의 요소중 증가 or 감소 or 증가하다가 감소 한다면 날카롭운 배열이 된다.

 

제약 사항

같은 수가 연속으로 온다면 날카로운 배열이 아니다.

주어진 배열의 원소를 감소시킬 수 있다.

 

#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <list>
#include <queue>
#include <deque>
//#include <map>
#include <set>
#include <stack>
#include <cstring>
 
using namespace std;
#define MAX_SIZE 100
#define INF 0x7fffffff
 
int main() {
 
    int t; cin >> t;
 
    while (t--) {
        
 
        int n; cin >> n;
 
        bool find = true;
        vector<int> origin(n);
        for (int i = 0; i < n; i++) cin >> origin[i];
        
        vector<int> assent(n);
        
        assent[0] = 0;
        for (int i = 1; i < n; i++) {
            if (assent[i - 1] != -1 && assent[i - 1] < origin[i]) {
                assent[i] = i;
            }
            else {
                assent[i] = -1;
            }
        }
        vector<int> rev = origin;
        reverse(rev.begin(), rev.end());
        vector<int> dessent(n);
        dessent[0] = 0;
        for (int i = 1; i < n; i++) {
            if (dessent[i - 1] != -1 && dessent[i - 1] < rev[i]) {
                dessent[i] = i;
            }
            else {
                dessent[i] = -1;
            }
        }
 
        int cand = 0;
        for (int i = 0; i < n; i++) {
            if (dessent[i] == -1)
                cand++;
            if (assent[i] == -1)
                cand++;
        }
 
        if (cand < n) {
            cout << "Yes" << "\n";
        }
        else {
            cout << "No" << "\n";
        }
 
    }
    return 0;
}