#388976 (Java) No.905 Sorted?

• 問題: No.905 Sorted?
• ユーザー: kitakitalily
• 提出日時: 2019-10-11 22:02:23
• 言語: Java (openjdk 23)
• 結果: AC
• 実行時間: 1,040 ms / 2,000 ms
• コード長: 5,116 bytes
• コンパイル時間: 2,290 ms
• コンパイル使用メモリ: 77,916 KB
• 実行使用メモリ: 69,332 KB
• 最終ジャッジ日時: 2024-11-25 07:29:15
• 合計ジャッジ時間: 13,682 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

ファイルパターン	結果
other	AC * 23

ソースコード

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
import java.util.*;
import java.io.*;
public class Main {
    static long mod = 1000000007;
    static int INF = 1000000000;
    public static void main(String[] args){
        FastScanner scanner = new FastScanner();
        int n = scanner.nextInt();
        long[] a = new long[n];
        for(int i = 0; i < n; i++){
            a[i] = scanner.nextLong();
        }
        int[] ulen = new int[n]; //ulen[i]:=i番目の値から単調増加である長さ
        int[] dlen = new int[n]; //dlen[i]:=i番目の値から単調現象である長さ
        int cnt = 1;
        ulen[n-1] = 1;
        for(int i = n-1; i >= 1; i--){
            if(a[i-1] <= a[i]){
                cnt++;
                ulen[i-1] = cnt;
            }else{
                cnt = 1;
                ulen[i-1] = cnt;
            }
        }
        dlen[n-1] = 1;
        for(int i = n-1; i >= 1; i--){
            if(a[i-1] >= a[i]){
                cnt++;
                dlen[i-1] = cnt;
            }else{
                cnt = 1;
                dlen[i-1] = cnt;
            }
        }
        int q = scanner.nextInt();
        for(int query = 0; query < q; query++){
            int l = scanner.nextInt();
            int r = scanner.nextInt();
            if(l+ulen[l]-1 >= r){
                System.out.print(1+ " ");
            }else{
                System.out.print(0 + " ");
            }
            if(l+dlen[l]-1 >= r){
                System.out.print(1 + " ") ;
            }else{
                System.out.print(0 + " ");
            }
            System.out.println();
        }
    }
    static class BIT{
        int n;
        int[] bit;
        public BIT(int n){
            this.n = n;
            bit = new int[n+1];
        }
        void add(int idx, int val){
            for(int i = idx+1; i <= n; i += i&(-i)) bit[i-1] += val;
        }
        int sum(int idx){
            int res = 0;
            for(int i = idx+1; i > 0; i -= i&(-i)) res += bit[i-1];
            return res;
        }
        int sum(int begin, int end){
            if(begin == 0) return sum(end);
            return sum(end)-sum(begin-1);
        }
    }
    static class Pair implements Comparable<Pair>{
    int first, second;
    Pair(int a, int b){
        first = a;
        second = b;
    }
    @Override
    public boolean equals(Object o){
        if (this == o) return true;
        if (!(o instanceof Pair)) return false;
        Pair p = (Pair) o;
        return first == p.first && second == p.second;
    }
    @Override
    public int compareTo(Pair p){
        return first == p.first ? second - p.second : first - p.first; //firstで昇順にソート
        //return (first == p.first ? second - p.second : first - p.first) * -1; //firstで降順にソート
        //return second == p.second ? first - p.first : second - p.second;//secondで昇順にソート
        //return (second == p.second ? first - p.first : second - p.second)*-1;//secondで降順にソート
            //return first * 1.0 / second > p.first * 1.0 / p.second ? 1 : -1; // first/secondの昇順にソート
            //return first * 1.0 / second < p.first * 1.0 / p.second ? 1 : -1; // first/secondの降順にソート
                //return second * 1.0 / first > p.second * 1.0 / p.first ? 1 : -1; // second/firstの昇順にソート
            //return second * 1.0 / first < p.second * 1.0 / p.first ? 1 : -1; // second/firstの降順にソート
                //return Math.atan2(second, first) > Math.atan2(p.second, p.first) ? 1 : -1; // second/firstの昇順にソート
                //return first + second > p.first + p.second ? 1 : -1; //first+secondの昇順にソート
                //return first + second < p.first + p.second ? 1 : -1; //first+secondの降順にソート
                //return first - second < p.first - p.second ? 1 : -1; //first-secondの降順にソート
        }
  }
    private static class FastScanner {
        private final InputStream in = System.in;
        private final byte[] buffer = new byte[1024];
        private int ptr = 0;
        private int buflen = 0;
        private boolean hasNextByte() {
                if (ptr < buflen) {
                        return true;
                }else{
                        ptr = 0;
                        try {
                                buflen = in.read(buffer);
                        } catch (IOException e) {
                                e.printStackTrace();
                        }
                        if (buflen <= 0) {
                                return false;
                        }
                }
                return true;
        }
        private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
        private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
        public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
        public String next() {
                if (!hasNext()) throw new NoSuchElementException();
                StringBuilder sb = new StringBuilder();
                int b = readByte();
                while(isPrintableChar(b)) {
                        sb.appendCodePoint(b);
                        b = readByte();
                }
                return sb.toString();
        }
        public long nextLong() {
                if (!hasNext()) throw new NoSuchElementException();
                long n = 0;
                boolean minus = false;
                int b = readByte();
                if (b == '-') {
                        minus = true;
                        b = readByte();
                }
                if (b < '0' || '9' < b) {
                        throw new NumberFormatException();
                }
                while(true){
                        if ('0' <= b && b <= '9') {
                                n *= 10;
                                n += b - '0';
                        }else if(b == -1 || !isPrintableChar(b)){
                                return minus ? -n : n;
                        }else{
                                throw new NumberFormatException();
                        }
                        b = readByte();
                }
        }
        public int nextInt() {
                long nl = nextLong();
                if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
                return (int) nl;
        }
        public double nextDouble() { return Double.parseDouble(next());}
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX