코드 복사/붙여넣기 하는 당신이 아름답습니다.

15670 : 도로 공사

풀이

구현이 좀 귀찮은데

잘 따져서 슥슥 짜주면 된다.

코드

#include <cstdio>

int n, m, i, x, y, a[100002];
int inc[100002], dec[100002];

int main() {
    scanf("%d %d", &n, &m);
    for (i = 1; i <= n; i++) scanf("%d", &a[i]);

    inc[1] = dec[1] = 1;
    for (i = 2; i <= n; i++) inc[i] = inc[i - 1] + (a[i - 1] >= a[i]);
    for (i = 2; i <= n; i++) dec[i] = dec[i - 1] + (a[i - 1] <= a[i]);

    for (i = 1; i <= m; i++) {
        scanf("%d %d", &x, &y);
        int ans = (inc[x - 1] + inc[n] - inc[y]) + (dec[y] - dec[x - 1]);
        if (x - 1 >= 1) ans += (a[x - 1] > a[x]) - (a[x - 1] < a[y]);
        if (y + 1 <= n) ans += (a[y] < a[y + 1]) - (a[x] < a[y + 1]);
        printf("%d\n", ans);
    }

    return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-06-24 21:47

Read more posts by this author