oj.uz

Submission #647705

# Submission time Handle Problem Language Result Execution time Memory
647705 2022-10-03T17:12:02 Z Iliya Balloons (CEOI11_bal) C++17
100 / 100
 224 ms 7372 KB 
#include <bits/stdc++.h>
using namespace std;

double radius(pair<double, double> a, double x){
	return (a.first - x) * (a.first - x) / (4 * a.second);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int n;
	cin >> n;
	vector<double> ans(n);
	stack<pair<double, double>> st;
	for(int i = 0; i < n; i++){
		double x, r;
		cin >> x >> r;
		while(!st.empty()){
			double tmp = radius(st.top(), x);
			r = min(r, tmp);
			if(r >= st.top().second) st.pop();
			else break;
		}
		ans[i] = r;
		st.push({x, r});
	}
	cout << fixed << setprecision(5);
	for(auto i : ans)
		cout << i << '\n';
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 940 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 2124 KB 50000 numbers
2 Correct 50 ms 2072 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 3648 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 4292 KB 115362 numbers
2 Correct 117 ms 4596 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 5576 KB 154271 numbers
2 Correct 190 ms 7372 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 6660 KB 200000 numbers
2 Correct 202 ms 7360 KB 199945 numbers