Algorithm-practice/src/Stack/P2867/Main.java at master · Seogeurim/Algorithm-practice · GitHub

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
package Stack.P2867;

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

public class Main {

    static int N;
    static int[] nums;

    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("src/Stack/P2867/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        nums = new int[N];
        for (int i = 0; i < N; i++) nums[i] = Integer.parseInt(br.readLine());

        Stack<Integer> stack = new Stack<>();

        int[] LM = new int[N];
        for (int i = 0; i < N; i++) {
            while (!stack.empty() && (nums[stack.peek()] <= nums[i])) stack.pop();
            LM[i] = stack.empty() ? 0 : stack.peek() + 1;
            stack.push(i);
        }

        stack.clear();
        int[] RM = new int[N];
        for (int i = N-1; i >= 0; i--) {
            while (!stack.empty() && (nums[stack.peek()] < nums[i])) stack.pop();
            RM[i] = stack.empty() ? N-1 : stack.peek() - 1;
            stack.push(i);
        }

        stack.clear();
        int[] lm = new int[N];
        for (int i = 0; i < N; i++) {
            while (!stack.empty() && (nums[stack.peek()] >= nums[i])) stack.pop();
            lm[i] = stack.empty() ? 0 : stack.peek() + 1;
            stack.push(i);
        }

        stack.clear();
        int[] rm = new int[N];
        for (int i = N-1; i >= 0; i--) {
            while (!stack.empty() && (nums[stack.peek()] > nums[i])) stack.pop();
            rm[i] = stack.empty() ? N-1 : stack.peek() - 1;
            stack.push(i);
        }

        long ans = 0;
        for (int i = 0; i < N; i++) {
            ans += nums[i] * (long)(i- LM[i] + 1) * (long)(RM[i] - i + 1);
            ans -= nums[i] * (long)(i- lm[i] + 1) * (long)(rm[i] - i + 1);
        }

        System.out.println(ans);
    }
}