[Gold II] Cow Frisbee - 24492

문제 링크

성능 요약

메모리: 54876 KB, 시간: 516 ms

분류

자료 구조, 스택

제출 일자

2025년 3월 22일 17:44:04

문제 설명

Farmer John's $N$ cows ($N \leq 3 \times 10^5)$ have heights $1, 2, \ldots, N$. One day, the cows are standing in a line in some order playing frisbee; let $h_1 \ldots h_N$ denote the heights of the cows in this order (so the $h$'s are a permutation of $1 \ldots N$).

Two cows at positions $i$ and $j$ in the line can successfully throw the frisbee back and forth if and only if every cow between them has height lower than $\min(h_i, h_j)$.

Please compute the sum of distances between all pairs of locations $i<j$ at which there resides a pair of cows that can successfully throw the frisbee back and forth. The distance between locations $i$ and $j$ is $j-i+1$.

입력

The first line of input contains a single integer $N$. The next line of input contains $h_1 \ldots h_N$, separated by spaces.

출력

Output the sum of distances of all pairs of locations at which there are cows that can throw the frisbee back and forth. Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).

문제 풀이

양 방향을 보기 위해 왼->오 와 오->왼 두 번 진행해줬다.

Stack 자료구조를 사용해 자신보다 큰것이 top에 있으면 자신을 넣고, 그게 아니라 자기보다 작은것이면 빼면서 거리계산해줬다.

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    class Cow{
        int idx, height;
        public Cow(int idx, int height){
            this.idx = idx;
            this.height = height;
        }
    }
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_24492_CowFrisbee/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Stack<Cow> stack_LtoR = new Stack<>();
        long res = 0;
        for(int i = 0; i < N; i++) {
            Cow currCow = new Cow(i, arr[i]);
            while(!stack_LtoR.isEmpty()) {
                if(stack_LtoR.peek().height < currCow.height) {
                    Cow tmpCow = stack_LtoR.pop();
                    res += currCow.idx - tmpCow.idx + 1;
                }
                else break;
            }
            stack_LtoR.push(currCow);
        }

        Stack<Cow> stack_RtoL = new Stack<>();
        for(int i = N-1; i >=0; i--) {
            Cow currCow = new Cow(i, arr[i]);
            while(!stack_RtoL.isEmpty()) {
                if(stack_RtoL.peek().height < currCow.height) {
                    Cow tmpCow = stack_RtoL.pop();
                    res += tmpCow.idx - currCow.idx + 1;
                }
                else break;
            }
            stack_RtoL.push(currCow);
        }
        System.out.println(res);
        br.close();
    }
}