oj.uz

Submission #866272

# Submission time Handle Problem Language Result Execution time Memory
866272 2023-10-25T16:57:59 Z dio_2 Balloons (CEOI11_bal) C++17
100 / 100
 115 ms 11816 KB 
#include<bits/stdc++.h>
using namespace std;

using ld = long double;
using ll = long long;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int N;
	cin >> N;
	
	vector<ll> x(N), r(N);
	vector<ld> ans(N);
	
	for(int i = 0;i < N;i++){
		cin >> x[i] >> r[i];
	}
	
	auto Calc = [&](int i, int j)->ld{
		ld radius_j = ans[j];
		return (ld(x[i]*x[i]+x[j]*x[j]-2*x[i]*x[j])) / (4 * radius_j);
	};
	
	//~ ans[0] = r[0];
	//~ cout << fixed << setprecision(3) << ans[0] << '\n';
	
	//~ for(int i = 1;i < N;i++){ O(N^2) BRUTE FORCE
		//~ ld use = r[i];
		//~ for(int j = 0;j < i;j++){
			//~ use = min(use, Calc(i, j));
		//~ }
		//~ ans[i] = use;
		//~ cout << fixed << setprecision(3) << use << '\n';
	//~ }
	
	stack<int> st;
	for(int i = 0;i < N;i++){
		ld res = r[i];
		while(!st.empty()){
			int id = st.top();
			res = min(res, Calc(i, id));
			if(res >= ans[id]) st.pop();
			else break;
		}
		ans[i] = res;
		st.push(i);
		cout << fixed << setprecision(3) << res << '\n';
	}
	
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1116 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2396 KB 50000 numbers
2 Correct 27 ms 3220 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 4432 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 4880 KB 115362 numbers
2 Correct 64 ms 7252 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 6484 KB 154271 numbers
2 Correct 114 ms 11816 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 8264 KB 200000 numbers
2 Correct 113 ms 11700 KB 199945 numbers