oj.uz

Submission #908598

# Submission time Handle Problem Language Result Execution time Memory
908598 2024-01-16T14:52:54 Z roimu Balloons (CEOI11_bal) C++14
100 / 100
 488 ms 14932 KB 
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <limits>
#include <assert.h>

using namespace std;

typedef long long LL;
//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18

long double dist(pair<long double, long double> a, pair<long double, long double> b) {
	long double four = 4.0000000000000000;
	return (a.first - b.first)*(a.first - b.first) / four / a.second;
}

long double getr(pair<long double, long double> a, pair<long double, long double> b) {
	return min(dist(a, b), b.second);
}


int main() {
	int n; cin >> n;
	vector<pair<long double, long double>> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i].first >> a[i].second;
	}

	vector<long double> ans(n);
	ans[0] = a[0].second;
	stack<pair<long double, long double>> st;
	st.push(a[0]);
	for (int i = 1; i < n; i++) {
		long double rnow = 10000000000;
		while (!st.empty()) {
			long double rb = getr(st.top(), a[i]);
			rnow = min(rnow, rb);
			if (rnow >= st.top().second) {
				st.pop();
			}
			else {
				break;
			}
		}

		if (st.empty()) {
			st.push({ a[i].first,rnow });
		}
		else {
			long double rb= getr(st.top(), a[i]);
			rnow = min(rnow, rb);
			st.push({ a[i].first,rnow });
		}

		ans[i] = rnow;
	}

	for (int i = 0; i < n; i++) {
		cout << fixed << setprecision(3) << ans[i] << endl;
	}

	return 0;
}

/*
2
0 2
20 10

*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 5 ms 348 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 1452 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 3376 KB 50000 numbers
2 Correct 124 ms 3288 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 6200 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 7252 KB 115362 numbers
2 Correct 283 ms 6748 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 9100 KB 154271 numbers
2 Correct 488 ms 14932 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 11348 KB 200000 numbers
2 Correct 481 ms 14908 KB 199945 numbers