oj.uz

Submission #490312

# Submission time Handle Problem Language Result Execution time Memory
490312 2021-11-27T00:18:01 Z Vectorized Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) Java 11
64 / 100
 3000 ms 206380 KB 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;
import java.util.StringTokenizer;

public class sortbooks {
    static int[] seg;
    static void update(int pos, int value, int n) {
        pos += n;
        seg[pos] = value;
        while (pos > 1) {
            pos >>= 1;
            seg[pos] = Math.max(seg[2 * pos], seg[2 * pos + 1]);
        }
    }
    static int range_query(int left, int right, int n) {
        right++;
        left += n;
        right += n;
        int mx = 0;
        while (left < right) {
            if ((left & 1) == 1) {
                mx = Math.max(mx, seg[left]);
                left++;
            }
            if ((right & 1) == 1) {
                right--;
                mx = Math.max(mx, seg[right]);
            }
            left /= 2;
            right /= 2;
        }
        return mx;
    }





    static class Range implements Comparable<Range>{
        int l, r, w;
        Range(int l, int r, int w){
            this.l = l;
            this.r = r;
            this.w = w;
        }
        public int compareTo(Range s){
            return l - s.l;
        }
    }

    static class Node{
        int r;
        int w;
        int ind;
        Node(int r, int w, int ind){
            this.r = r;
            this.w = w;
            this.ind = ind;
        }
    }

    @SuppressWarnings("unchecked")
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken());
        int[] ar = new int[n];
        st = new StringTokenizer(br.readLine());
        Stack<Integer> s = new Stack<Integer>();
        ArrayList<Range> range = new ArrayList<Range>();
        for (int i = 0; i < n; i++){
            ar[i] = Integer.parseInt(st.nextToken());
            while (s.size() > 0 && ar[s.peek()]<=ar[i]){s.pop();}
            if(s.size() > 0) range.add(new Range(s.peek(), i, ar[s.peek()] + ar[i]));
            s.add(i);
        }
        Collections.sort(range);
        ArrayList<Node>[] qs = new ArrayList[n];
        for (int i = 0; i < n; i++) qs[i] = new ArrayList<Node>();
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            qs[Integer.parseInt(st.nextToken()) - 1].add(new Node(Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken()), i));
        }
        seg = new int[2 * n];
        boolean[] ans = new boolean[m];
        int ind = range.size() - 1;
        for (int i = n - 1; i >= 0; i--) {
            //update
            while (ind >= 0 && range.get(ind).l >= i){
                update(range.get(ind).r, range.get(ind).w, n);
                ind--;
            }
            //process qs
            for (int j = 0; j < qs[i].size(); j++) {
                if(qs[i].get(j).w >= range_query(i, qs[i].get(j).r, n)){
                    ans[qs[i].get(j).ind] = true;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            System.out.println((ans[i] ? 1 : 0));
        }
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 8540 KB Output is correct
2 Correct 55 ms 8236 KB Output is correct
3 Correct 99 ms 8540 KB Output is correct
4 Correct 90 ms 8412 KB Output is correct
5 Correct 84 ms 8448 KB Output is correct
6 Correct 128 ms 10260 KB Output is correct
7 Correct 126 ms 10596 KB Output is correct
8 Correct 99 ms 8744 KB Output is correct
9 Correct 98 ms 8708 KB Output is correct
10 Correct 99 ms 8528 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 8540 KB Output is correct
2 Correct 55 ms 8236 KB Output is correct
3 Correct 99 ms 8540 KB Output is correct
4 Correct 90 ms 8412 KB Output is correct
5 Correct 84 ms 8448 KB Output is correct
6 Correct 128 ms 10260 KB Output is correct
7 Correct 126 ms 10596 KB Output is correct
8 Correct 99 ms 8744 KB Output is correct
9 Correct 98 ms 8708 KB Output is correct
10 Correct 99 ms 8528 KB Output is correct
11 Correct 342 ms 13824 KB Output is correct
12 Correct 387 ms 14196 KB Output is correct
13 Correct 392 ms 14064 KB Output is correct
14 Correct 550 ms 14364 KB Output is correct
15 Correct 556 ms 14512 KB Output is correct
16 Correct 564 ms 14148 KB Output is correct
17 Correct 534 ms 14416 KB Output is correct
18 Correct 516 ms 14428 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3073 ms 206380 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1378 ms 38896 KB Output is correct
2 Correct 1398 ms 35064 KB Output is correct
3 Correct 1156 ms 32288 KB Output is correct
4 Correct 1166 ms 32904 KB Output is correct
5 Correct 1170 ms 33032 KB Output is correct
6 Correct 1208 ms 30268 KB Output is correct
7 Correct 1151 ms 30180 KB Output is correct
8 Correct 1282 ms 36052 KB Output is correct
9 Correct 980 ms 24464 KB Output is correct
10 Correct 1234 ms 35692 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 8540 KB Output is correct
2 Correct 55 ms 8236 KB Output is correct
3 Correct 99 ms 8540 KB Output is correct
4 Correct 90 ms 8412 KB Output is correct
5 Correct 84 ms 8448 KB Output is correct
6 Correct 128 ms 10260 KB Output is correct
7 Correct 126 ms 10596 KB Output is correct
8 Correct 99 ms 8744 KB Output is correct
9 Correct 98 ms 8708 KB Output is correct
10 Correct 99 ms 8528 KB Output is correct
11 Correct 342 ms 13824 KB Output is correct
12 Correct 387 ms 14196 KB Output is correct
13 Correct 392 ms 14064 KB Output is correct
14 Correct 550 ms 14364 KB Output is correct
15 Correct 556 ms 14512 KB Output is correct
16 Correct 564 ms 14148 KB Output is correct
17 Correct 534 ms 14416 KB Output is correct
18 Correct 516 ms 14428 KB Output is correct
19 Correct 1883 ms 59756 KB Output is correct
20 Correct 1884 ms 59472 KB Output is correct
21 Correct 1855 ms 56616 KB Output is correct
22 Correct 1879 ms 56680 KB Output is correct
23 Correct 1906 ms 56892 KB Output is correct
24 Correct 1570 ms 44904 KB Output is correct
25 Correct 1548 ms 45044 KB Output is correct
26 Correct 1614 ms 49052 KB Output is correct
27 Correct 1587 ms 49060 KB Output is correct
28 Correct 1583 ms 51092 KB Output is correct
29 Correct 1626 ms 53548 KB Output is correct
30 Correct 1607 ms 53460 KB Output is correct
31 Correct 1622 ms 53496 KB Output is correct
32 Correct 1608 ms 53696 KB Output is correct
33 Correct 1637 ms 53412 KB Output is correct
34 Correct 1553 ms 45032 KB Output is correct
35 Correct 1543 ms 44788 KB Output is correct
36 Correct 1581 ms 44804 KB Output is correct
37 Correct 1545 ms 44872 KB Output is correct
38 Correct 1567 ms 44928 KB Output is correct
39 Correct 1753 ms 51892 KB Output is correct
40 Correct 1647 ms 46820 KB Output is correct
41 Correct 1715 ms 54620 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 8540 KB Output is correct
2 Correct 55 ms 8236 KB Output is correct
3 Correct 99 ms 8540 KB Output is correct
4 Correct 90 ms 8412 KB Output is correct
5 Correct 84 ms 8448 KB Output is correct
6 Correct 128 ms 10260 KB Output is correct
7 Correct 126 ms 10596 KB Output is correct
8 Correct 99 ms 8744 KB Output is correct
9 Correct 98 ms 8708 KB Output is correct
10 Correct 99 ms 8528 KB Output is correct
11 Correct 342 ms 13824 KB Output is correct
12 Correct 387 ms 14196 KB Output is correct
13 Correct 392 ms 14064 KB Output is correct
14 Correct 550 ms 14364 KB Output is correct
15 Correct 556 ms 14512 KB Output is correct
16 Correct 564 ms 14148 KB Output is correct
17 Correct 534 ms 14416 KB Output is correct
18 Correct 516 ms 14428 KB Output is correct
19 Execution timed out 3073 ms 206380 KB Time limit exceeded
20 Halted 0 ms 0 KB -