oj.uz

Submission #569868

# Submission time Handle Problem Language Result Execution time Memory
569868 2022-05-28T02:46:01 Z Karnis_052 Balloons (CEOI11_bal) C++17
100 / 100
 539 ms 7032 KB 
// Bismillahir Rahmanir Rahim
#include<bits/stdc++.h>
using namespace std;
typedef long long int  ll;
typedef pair<int, int>PI;
typedef pair<ll, ll > PL;
typedef vector<int>VI;
typedef vector<ll>VL;
#define FF first
#define SS second
const int mod = 1e9 + 7;
const int INF = 1e9;
const int N = 1e5 + 5;
// it's a oj.uz problem
int main()
{
	ios::sync_with_stdio(false);   cin.tie(0); cout.tie(0);
	int n;
	cin >> n;
	stack < pair<double, double>>st;
	for (int i = 0; i < n; i++)
	{
		long double x, r;
		cin >> x >> r;
		while (!st.empty())
		{
			long double x1 = st.top().FF, r1 = st.top().SS;
			long double nw = (x1 - x) * (x1 - x) / (4 * r1);
			r = min(r, nw);
			if (r >= r1)
				st.pop();
			else break;

		}
		st.push({x, r});
		cout << fixed << setprecision(3);
		cout << r << endl;
	}

	cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl;
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 372 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 884 KB 50000 numbers
2 Correct 126 ms 1968 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 1252 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 1420 KB 115362 numbers
2 Correct 284 ms 3360 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 1820 KB 154271 numbers
2 Correct 492 ms 7032 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 1824 KB 200000 numbers
2 Correct 539 ms 5400 KB 199945 numbers