oj.uz

Submission #542785

# Submission time Handle Problem Language Result Execution time Memory
542785 2022-03-28T03:52:24 Z shcal Balloons (CEOI11_bal) Java 11
70 / 100
 2000 ms 33788 KB 
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.util.Stack;
import java.util.StringTokenizer;

// https://oj.uz/problem/view/CEOI11_bal
public class bal {
	public static void main(String[] args) throws IOException {
		FastIO io = new FastIO();
		
		int n = io.nextInt();
		
		Stack<Integer> s = new Stack<>();
		
		double[] px = new double[n];
		double[] pr = new double[n];
		
		StringTokenizer token;
		for (int i = 0; i < n; i++) {
			double x = io.nextDouble();
			double r = io.nextDouble();
			
			while (!s.isEmpty()) {
				int t = s.peek();
				double x1 = px[t];
				double r1 = pr[t];
				r = Math.min(r, (x-x1)*(x-x1)/(4.0*r1));
				if (r >= r1) s.pop();
				else break;
			}
			
			io.printf("%.3f\n", r);
			
			px[i] = x;
			pr[i] = r;
			s.push(i);
		}
		
		io.close();
	}
}

class FastIO extends PrintWriter {
	private InputStream stream;
	private byte[] buf = new byte[1 << 16];
	private int curChar;
	private int numChars;

	// standard input
	public FastIO() { this(System.in, System.out); }

	public FastIO(InputStream i, OutputStream o) {
		super(o);
		stream = i;
	}

	// file input
	public FastIO(String i, String o) throws IOException {
		super(new FileWriter(o));
		stream = new FileInputStream(i);
	}

	// throws InputMismatchException() if previously detected end of file
	private int nextByte() {
		if (numChars == -1) {
			throw new InputMismatchException();
		}
		if (curChar >= numChars) {
			curChar = 0;
			try {
				numChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (numChars == -1) {
				return -1;  // end of file
			}
		}
		return buf[curChar++];
	}

	// to read in entire lines, replace c <= ' '
	// with a function that checks whether c is a line break
	public String next() {
		int c;
		do {
			c = nextByte();
		} while (c <= ' ');

		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = nextByte();
		} while (c > ' ');
		return res.toString();
	}

	public int nextInt() {  // nextLong() would be implemented similarly
		int c;
		do {
			c = nextByte();
		} while (c <= ' ');

		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = nextByte();
		}

		int res = 0;
		do {
			if (c < '0' || c > '9') {
				throw new InputMismatchException();
			}
			res = 10 * res + c - '0';
			c = nextByte();
		} while (c > ' ');
		return res * sgn;
	}

	public double nextDouble() { return Double.parseDouble(next()); }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 9680 KB 10 numbers

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 9324 KB 2 numbers

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 10456 KB 505 numbers

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 625 ms 19128 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1318 ms 22388 KB 20000 numbers

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1674 ms 26724 KB 115362 numbers
2 Correct 1254 ms 25000 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1843 ms 27572 KB 154271 numbers
2 Correct 1299 ms 26712 KB 200000 numbers

Subtask #10
0 / 10.0

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