oj.uz

Submission #542788

# Submission time Handle Problem Language Result Execution time Memory
542788 2022-03-28T03:59:01 Z shcal Balloons (CEOI11_bal) Java 11
100 / 100
 1965 ms 33200 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<Pair> s = new Stack<>();
		
		StringTokenizer token;
		for (int i = 0; i < n; i++) {
			double x = io.nextDouble();
			double r = io.nextDouble();
			
			while (!s.isEmpty()) {
				double x1 = s.peek().first;
				double r1 = s.peek().second;
				r = Math.min(r, (x-x1)*(x-x1)/(4.0*r1));
				if (r >= r1) s.pop();
				else break;
			}
			
			io.printf("%.3f\n", r);
			
			s.push(new Pair(x, r));
		}
		
		io.close();
	}
}

class Pair {
	double first;
	double second;
	
	public Pair (double f, double s) {
		first = f;
		second = s;
	}
}

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 78 ms 9320 KB 10 numbers

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 9408 KB 2 numbers

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 10064 KB 505 numbers

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 561 ms 19272 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1260 ms 22064 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1893 ms 33200 KB 50000 numbers
2 Correct 1051 ms 23376 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1965 ms 31624 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1523 ms 25124 KB 115362 numbers
2 Correct 1142 ms 22644 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1711 ms 25328 KB 154271 numbers
2 Correct 1208 ms 23300 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1915 ms 28388 KB 200000 numbers
2 Correct 1205 ms 27164 KB 199945 numbers