oj.uz

답안 #405684

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
405684 2021-05-16T17:41:31 Z huukhang Balloons (CEOI11_bal) C++11
100 / 100
 253 ms 10156 KB 
/*
						   Khangnh's code

“You can either experience the pain of discipline or the pain of regret. 
						The choice is yours.”
*/

// - Only when necessary :d
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
using namespace std;

#define fileopen(a, b) freopen(((string)a + ".inp").c_str(), "r", stdin); freopen(((string)b + ".out").c_str(), "w", stdout); 

#define ll long long
#define ld long double
#define int long long
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
typedef pair<int, int> pii;

const ll mod = 1e9 + 7;
const ll inf = 1e9 + 7;
const double eps = 1e-9;

int n;
int x[200005];
ld r[200005];
stack<pair<int, ld>> st;

ld inflate(int x0, ld r0) {
	while (!st.empty()) {
		pair<int, ld> k = st.top();
		int tmp = (k.fi - x0)*(k.fi - x0);
		r0 = min(r0, tmp/(4*k.se));

		if (r0 >= k.se) st.pop();
		else break;
	}
	st.push({x0, r0});

	return r0;
}

void solve() {
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> x[i] >> r[i];

	cout << fixed << setprecision(3);
	for (int i = 1; i <= n; ++i) cout << inflate(x[i], r[i]) << "\n";
}

signed main() {
	#ifdef LOCAL
		fileopen("input", "output");
		auto start = clock();
	#endif
	#ifndef LOCAL
//		fileopen("LAH", "LAH");
	#endif
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t = 1;
//	cin >> t;
	while (t--) solve();
	#ifdef LOCAL
		auto end = clock();
		cout << "\n\nExecution time : " << double(end - start)/CLOCKS_PER_SEC << "[s]";
	#endif
	return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB 10 numbers

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB 2 numbers

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB 505 numbers

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 332 KB 2000 numbers

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 936 KB 20000 numbers

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 2220 KB 50000 numbers
2 Correct 52 ms 2732 KB 49912 numbers

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 114 ms 3748 KB 100000 numbers

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 154 ms 4284 KB 115362 numbers
2 Correct 120 ms 6164 KB 119971 numbers

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 168 ms 5540 KB 154271 numbers
2 Correct 197 ms 10156 KB 200000 numbers

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 211 ms 6724 KB 200000 numbers
2 Correct 253 ms 10112 KB 199945 numbers