Submission #516245

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
516245	2022-01-20T19:22:00 Z	gumbymoo	Mountain Trek Route (IZhO12_route)	Java 11	0 / 100	60 ms	8760 KB

route

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Stack;
import java.util.StringTokenizer;

public class route {
	
	static class Element {
		
		int val, index;
		
		public Element(int val, int index) {
			this.val = val; this.index = index;
		}
		
	}
	
	static class Range implements Comparable<Range> {
		
		int l, r;
		int height;
		
		public Range(int l, int r, int height) {
			this.l = l; this.r = r; this.height = height;
		}

		@Override
		public int compareTo(Range o) {
			if(height - o.height == 0)
				return (r - l + 1) - (o.r - o.l + 1);
			return height - o.height;
		}
		
	}
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		
		int[] a = new int[n];
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++)
			a[i] = Integer.parseInt(st.nextToken());
		
		int[] leftBiggerElement = new int[n];
		int[] rightBiggerElement = new int[n];
		//technically greater than or equal to
		//need to avoid double counting
		
		Arrays.fill(leftBiggerElement, -1);
		Arrays.fill(rightBiggerElement, -1);
		
		Stack<Element> decreasing = new Stack<Element>();
		ArrayList<Range> ranges = new ArrayList<Range>();
		
		for(int i = 0; i < 2*n; i++) {
			int index = i % n;
			while(!decreasing.isEmpty() && decreasing.peek().val < a[index])
				decreasing.pop();
			if(leftBiggerElement[index] == -1 && !decreasing.isEmpty()) {
				leftBiggerElement[index] = decreasing.peek().index;
				if(Math.abs(i - leftBiggerElement[index]) > 1)
					ranges.add(new Range(leftBiggerElement[index], i, Math.min(a[leftBiggerElement[index] % n], a[index])));
			}
			decreasing.push(new Element(a[index], i));
		}
		
		decreasing = new Stack<Element>();
		
		for(int i = 2*n-1; i >= 0; i--) {
			int index = i % n;
			while(!decreasing.isEmpty() && decreasing.peek().val < a[index])
				decreasing.pop();
			if(rightBiggerElement[index] == -1 && !decreasing.isEmpty()) {
				rightBiggerElement[index] = decreasing.peek().index;
				if(Math.abs(rightBiggerElement[index] - i) > 1)
					ranges.add(new Range(i,rightBiggerElement[index],Math.min(a[rightBiggerElement[index] % n], a[index])));
			}
			decreasing.push(new Element(a[index],i));
		}
		
		Collections.sort(ranges);
		int numRanges = ranges.size();
		
		int blocksLeft = k;
		int currentRange = 0;
		int reduction = 0;
		int lastL = -1;
		int lastR = -1;
		while(blocksLeft > 0 && currentRange < numRanges) {
			Range range = ranges.get(currentRange);
			int rangeLength = range.r - range.l - 1;
			if(rangeLength > blocksLeft)
				break;
			if((lastL%n) == (range.l%n) && (lastR%n) == (range.r%n)) {
				currentRange++;
				continue;
			}
			lastL = range.l;
			lastR = range.r;
			blocksLeft -= rangeLength;
			reduction += 2;
			currentRange++;
		}
		
		
		pw.println(reduction);
		
		/*
		for(Range range : ranges)
			pw.println(range.l + " " + range.r + " " + range.height);
			*/
			
		pw.close();
		
	}

}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	56 ms	8760 KB	Output is correct
2	Correct	60 ms	8284 KB	Output is correct
3	Incorrect	58 ms	8592 KB	Output isn't correct
4	Halted	0 ms	0 KB	-