https://www.acmicpc.net/problem/14009

핵심 아이디어

<aside> 💡

케이스를 아래와 같이 분류하며 길이를 최대한 늘려나가면 된다.

• 이전과 현재 값이 같은 경우 - 구간 초기화
• 이전 두 값이 같은 경우 - 증가, 감소 상관없이 구간 증가
• 이전에 증가한 경우
  • 현재도 증가한 경우 - 구간 초기화
  • 현재 감소한 경우 - 구간 증가
• 이전에 감소한 경우
  • 현재도 감소한 경우 - 구간 초기화
  • 현재 증가한 경우 - 구간 증가 </aside>

코드

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
using namespace std;
typedef long long ll;

int n;
int a[200'001];

ll ans = 0;
int state = 0;
int prv;

signed main()
{
    FASTIO;
    cin >> n;
    for(int i = 0; i<n; i++) cin >> a[i];

    if(n == 1){
        cout << 1;
        return 0;
    }

    prv = a[0];
    int sidx = 0;

    for(int i = 0; i<n; i++){
        if(prv == a[i]){
            ans += 1LL*(i-sidx)*(i-sidx+1)/2;
            sidx = i;
            state = 0;

            // cout << 0 <<":" << i <<", "<< ans<<"\\n";
        }

        else if(state == 0){
            if(prv<a[i]) state = 1;
            else state = -1;
        }
        
        else if(state == 1){
            if(prv<a[i]){
                ans += 1LL*(i-sidx)*(i-sidx+1)/2-1;
                sidx = i-1;
                state = 1;

                // cout << 1 <<":" << i <<", "<< ans<<"\\n";
            }
            else state = -1;
        }
        else if(state == -1){
            if(prv>a[i]){
                ans += 1LL*(i-sidx)*(i-sidx+1)/2-1;
                sidx = i-1;
                state = -1;

                // cout << -1 <<":" << i <<", "<< ans<<"\\n";
            }
            else state = 1;
        }

        prv = a[i];
    }
    ans += 1LL*(n-sidx)*(n-sidx+1)/2;
    
    cout << ans;
    
    return 0;
}