Submission #542785

#	Time	Username	Problem	Language	Result	Execution time	Memory
542785		shcal	Balloons (CEOI11_bal)	Java	70 / 100	2067 ms	33788 KiB

bal

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 0 / 10