Submission #490312

#	Time	Username	Problem	Language	Result	Execution time	Memory
490312		Vectorized	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	Java	64 / 100	3073 ms	206380 KiB

sortbooks

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 / 8
• Subtask 2: 9 / 9
• Subtask 3: 0 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 0 / 23