oj.uz

Submission #831269

# Submission time Handle Problem Language Result Execution time Memory
831269 2023-08-20T03:34:26 Z tranxuanbach Balloons (CEOI11_bal) C++17
100 / 100
 174 ms 7876 KB 
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;

const int N = 2e5 + 5;

int n;
vector <pair <int, double>> a;

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	// freopen("KEK.inp", "r", stdin);
	// freopen("KEK.out", "w", stdout);
	cout << fixed << setprecision(15);
	cin >> n;
	while (n--){
		int x, max_r;
		cin >> x >> max_r;
		double r = max_r;
		while (not a.empty()){
			auto [tx, tr] = a.back();
			r = min(r, (ll)(x - tx) * (x - tx) / (4ll * tr));
			if (r < tr){
				break;
			}
			a.pop_back();
		}
		a.emplace_back(x, r);
		cout << r << endl;
	}
}

/*
==================================================+
INPUT                                             |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

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 1 ms 212 KB 505 numbers

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 684 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 1564 KB 50000 numbers
2 Correct 33 ms 2220 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 2608 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 3004 KB 115362 numbers
2 Correct 79 ms 4852 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 3732 KB 154271 numbers
2 Correct 121 ms 7808 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 4364 KB 200000 numbers
2 Correct 119 ms 7876 KB 199945 numbers