oj.uz

Submission #1005719

# Submission time Handle Problem Language Result Execution time Memory
1005719 2024-06-22T22:29:26 Z Username_taken12 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) Java 11
0 / 100
 3000 ms 124988 KB 
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][3];
		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--){
			int[] it = new int[]{-1,-1};
			while(a[i]>stack.peek()[0]){
				it=stack.pop();
				while(true){
					int next=map.ceilingKey(it[1]);
					if(map.get(next)<=it[0]+a[i])
						map.remove(it[1]);
					else
						break;
				}
				map.put(i,it[0]+a[i]);
			}
			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][i]));
				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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 24516 KB Output is correct
2 Correct 45 ms 22564 KB Output is correct
3 Execution timed out 3043 ms 23600 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 24516 KB Output is correct
2 Correct 45 ms 22564 KB Output is correct
3 Execution timed out 3043 ms 23600 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 644 ms 35960 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 24516 KB Output is correct
2 Correct 45 ms 22564 KB Output is correct
3 Execution timed out 3043 ms 23600 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 24516 KB Output is correct
2 Correct 45 ms 22564 KB Output is correct
3 Execution timed out 3043 ms 23600 KB Time limit exceeded
4 Halted 0 ms 0 KB -