oj.uz

Submission #486572

# Submission time Handle Problem Language Result Execution time Memory
486572 2021-11-12T03:56:15 Z erlkonig Balloons (CEOI11_bal) C++14
100 / 100
 259 ms 9284 KB 
// time-limit: 2000
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define ar array
#define fi first
#define se second
#define ii pair <int, int>
#define vt vector
#define pb push_back
#define sz(x) (int)(x).size()
#define reset(a, x) memset(a, x, sizeof(a))

#define F_OR(i, a, b, s) for (auto i=(a); (s)>0?i<=(b):i>=(b); i+=(s))
#define F_OR1(e) F_OR(i, 0, (e)-1, 1)
#define F_OR2(i, e) F_OR(i, 0, (e)-1, 1)
#define F_OR3(i, b, e) F_OR(i, (b), (e), 1)
#define F_OR4(i, b, e, s) F_OR(i, (b), (e), (s))
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define fo(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define each(x, a) for (auto& x: a)
#define END cerr << "\n";
#define endl "\n"

#define error(args...) { \
	string _s = #args; \
	replace(_s.begin(), _s.end(), ',', ' '); \
	stringstream _ss(_s); \
	istream_iterator <string> _it(_ss); \
	err(_it, args); \
}

void err(istream_iterator<string> it) {}

template<typename T, typename... Args> 
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << "=" << a << ", ";
	err(++it, args...);
}

template<class T> void read(T& x) {
	cin >> x;
}

template<class H, class... T> void read(H& h, T&... t) {
	read(h);
	read(t...);
}

template<class A> void write(A x) {
	cout << x;
}

template<class H, class... T> void write(const H& h, const T&... t) { 
	write(h);
	write(t...);
}

void print() {
	write("\n");
}

template<class H, class... T> void print(const H& h, const T&... t) { 
	write(h);
	if(sizeof...(t))
		write(' ');
	print(t...);
}

#define file ""

inline void setIO() {
	//freopen(file".out", "w", stdout); freopen(file".in", "r", stdin);
	cin.tie(0)->sync_with_stdio(0);
}

const long long INF = 2e18;
const int inf = 0x3c3c3c3c, N = 2e5;
stack <pair <ld, ld>> st;
int n;

ld InflateBalloon(ld x, ld r) {
    while (sz(st)) {
        ld x1 = st.top().fi, r1 = st.top().se;
        r = min(r, (x-x1)*(x-x1)/(4*r1));
        if (r > r1) st.pop();
        else break;
    }
    st.push({x, r});
    return r;
}

void solve() {
	cout << fixed << setprecision(6);
    read(n);
    fo(n) {
        ld x, r;
        read(x, r);
        print(InflateBalloon(x, r));
    }
}

int32_t main() {
	setIO();
	int Case = 1;
	//read(Case);
	fo(ttest, 1, Case) {
		//write("Case ", ttest, ": ");
		solve();
	}
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 740 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 1908 KB 50000 numbers
2 Correct 77 ms 2476 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 3184 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 3712 KB 115362 numbers
2 Correct 146 ms 5736 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 4640 KB 154271 numbers
2 Correct 211 ms 9240 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 5188 KB 200000 numbers
2 Correct 206 ms 9284 KB 199945 numbers