oj.uz

Submission #800858

# Submission time Handle Problem Language Result Execution time Memory
800858 2023-08-02T00:51:46 Z Callie Balloons (CEOI11_bal) Java 11
100 / 100
 1636 ms 34024 KB 
import java.io.*;
import java.util.*;

class Balloon {
	public long x;
	public double r;

	public Balloon(long x, double r) {
		this.x = x;
		this.r = r;
	}

	public double calcR(long bx) { 
		return (x - bx) * (x - bx) / (4 * r); 
	}
}

public class bal {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		
		int balloons = Integer.parseInt(in.readLine());
		double[] answers = new double[balloons];
		Stack<Balloon> s = new Stack<Balloon>();
		
		for(int i = 0; i < balloons; i++) {
			StringTokenizer st = new StringTokenizer(in.readLine());
			long x = Integer.parseInt(st.nextToken());
			double r = Integer.parseInt(st.nextToken());
			double max = r;
			
			while(!s.isEmpty()) {			
				double to = s.peek().calcR(x);			
				max = Math.min(max, to);
				
				if(max >= s.peek().r) {
					s.pop();
					continue;
				}
				else break;
			}
			
			s.add(new Balloon(x, max));
			answers[i] = max;
		}
		
		for(double i: answers) System.out.println(i);
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 8728 KB 10 numbers

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 8248 KB 2 numbers

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 8944 KB 505 numbers

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 15512 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 776 ms 19024 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1313 ms 33684 KB 50000 numbers
2 Correct 711 ms 18404 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1361 ms 34024 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1169 ms 28128 KB 115362 numbers
2 Correct 941 ms 21476 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1359 ms 29036 KB 154271 numbers
2 Correct 1122 ms 24960 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1636 ms 33364 KB 200000 numbers
2 Correct 1114 ms 25152 KB 199945 numbers