Submission #1005730

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005730		Username_taken12	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	Java	100 / 100	2140 ms	185564 KiB

sortbooks

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

public class sortbooks {
	public static void main(String[] args) throws IOException {
		BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);

		StringTokenizer st = new StringTokenizer(r.readLine());
		TreeMap<Integer,Integer> map = new TreeMap<>();
		map.put(-1, 0);
		Stack<int[]> stack = new Stack<>();
		stack.add(new int[]{2100000000, -100});
		int N = Integer.parseInt(st.nextToken());
		int Q = Integer.parseInt(st.nextToken());
		map.put(N+1, 2100000001);

		st = new StringTokenizer(r.readLine());
		int[] a = new int[N];
		for(int i=0; i<N; i++)
			a[i]=Integer.parseInt(st.nextToken());
		int[][] queries = new int[Q][4];
		for(int i=0; i<Q; i++)
		{
			st=new StringTokenizer(r.readLine());
			queries[i]=new int[]{Integer.parseInt(st.nextToken())-1, Integer.parseInt(st.nextToken())-1, Integer.parseInt(st.nextToken()), i};
		}

		Arrays.sort(queries, new Comp());
		boolean[] ans = new boolean[Q];
		int qp=0;
		for(int i=N-1; i>-1; i--){
			//System.out.println(i);
			int[] it = new int[]{-1,-1};
			//System.out.println(stack);
			while(a[i]>stack.peek()[0]){
				it=stack.pop();
				while(true){
					int next=map.ceilingKey(it[1]);
					//System.out.println(it[1]);
					if(map.get(next)<=it[0]+a[i])
						map.remove(next);
					else
						break;
					//System.out.println("True");
				}
				map.put(it[1],it[0]+a[i]);
				//System.out.println("around and around");
			}
			//System.out.println("exit");
			if(a[i]==stack.peek()[0])
				stack.pop();
			stack.add(new int[]{a[i], i});
			while(qp<Q&&i==queries[qp][0])
			{
				ans[queries[qp][3]]=queries[qp][2]>=map.get(map.floorKey(queries[qp][1]));
				qp++;
			}
		}
		for(int i=0; i<Q; i++)
			pw.println((ans[i] ? 1 : 0));
		pw.close();
	}
}
class Comp implements Comparator<int[]>{
	public int compare(int[] a, int[] b){
		return Integer.compare(-a[0],-b[0]);
	}
}

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 23 / 23