#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using db = long double; // or double, if TL is tight
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pdd = pair<db, db>;
#define mp make_pair
#define f first
#define s second
#define tcT template<class T
#define tcTU tcT, class U
tcT> using V = vector<T>;
tcT, size_t SZ> using AR = array<T,SZ>;
using vi = V<int>;
using vb = V<bool>;
using vl = V<ll>;
using vd = V<db>;
using vs = V<string>;
using vpii = V<pii>;
using vpll = V<pll>;
#define sz(x) int((x).size())
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sor(x) sort(all(x))
#define rz resize
#define ins insert
#define pb push_back
#define eb emplace_back
#define ft front()
#define bk back()
#define lb lower_bound
#define ub upper_bound
tcT> int lwb(V<T>& a, const T& b) { return int(lb(all(a),b)-begin(a)); }
tcT> int upb(V<T>& a, const T& b) { return int(ub(all(a),b)-begin(a)); }
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define rep(a) F0R(_,a)
#define each(a,x) for (auto& a: x)
const int MOD = 1e9+7; // 998244353;
const int MOD9 = 1e9+9;
const int MOD998 = 998244353;
const ll INF = 1e18; // not too close to LLONG_MAX
const db PI = acos((db)-1);
const int dx[4]{1,0,-1,0}, dy[4]{0,1,0,-1}; // for every grid problem!!
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
constexpr int pct(int x) { return __builtin_popcount(x); } // # of bits set
constexpr int clz(int x) { return __builtin_clz(x); } // # of bits set
constexpr int ctz(int x) { return __builtin_ctz(x); } // # of bits set
ll p2(int b) { return (1ll << b); }
int l2(int x) { return 31 - clz(x); }
int l2(ll x) { return 63 - clz(x); }
ll msum(ll a, ll b, ll m = MOD) { return ((a + b) % m + m) % m; }
ll mdif(ll a, ll b, ll m = MOD) { return ((a - b) % m + m) % m; }
ll mmul(ll a, ll b, ll m = MOD) { return (__int128)a * b % m; }
ll mexp(ll b, ll e, ll m = MOD) {
ll res = 1;
while (e) {
if (e % 2) res = mmul(res, b, m);
b = mmul(b, b, m);
e /= 2;
} return res;
}
ll exp(ll b, ll e) { return mexp(b, e, INF); }
ll inv(ll b, ll m = MOD) { return mexp(b, m-2, m); }
ll mdiv(ll a, ll b, ll m = MOD) { return mmul(a, inv(b), m); }
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down
tcT> bool ckmin(T& a, const T& b) {
return b < a ? a = b, 1 : 0; } // set a = min(a,b)
tcT> bool ckmax(T& a, const T& b) {
return a < b ? a = b, 1 : 0; } // set a = max(a,b)
//GNU Policy Based Data Structures
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> indexed_multiset;
//String Hash
long long compute_hash(const string &s) {
const int p = 31;
long long hash_value = 0;
long long p_pow = 1;
for (char c : s) {
hash_value = (hash_value + (c - 'a' + 1) * p_pow) % MOD9;
p_pow = (p_pow * p) % MOD9;
}
return hash_value;
}
//Z Function
vector<int> z_function(string s) {
int n = s.size();
vector<int> z(n);
int l = 0, r = 0;
for(int i = 1; i < n; i++) {
if(i < r) {
z[i] = min(r - i, z[i - l]);
}
while(i + z[i] < n && s[z[i]] == s[i + z[i]]) {
z[i]++;
}
if(i + z[i] > r) {
l = i;
r = i + z[i];
}
}
return z;
}
//DSU
struct DSU {
vi e; void init(int N) { e = vi(N,-1); }
int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
bool sameSet(int a, int b) { return get(a) == get(b); }
int size(int x) { return -e[get(x)]; }
bool unite(int x, int y) { // union by size
x = get(x), y = get(y); if (x == y) return 0;
if (e[x] > e[y]) swap(x,y);
e[x] += e[y]; e[y] = x; return 1;
}
};
//Segment Tree
struct SegTree {
typedef int T;
static constexpr T unit = 0;
T f(T a, T b) { return a+b; } // (any associative fn)
vector<T> s; int n;
SegTree(int n = 0, T def = unit) : s(2*n, def), n(n) {}
void update(int pos, T val) {
for (s[pos += n] = val; pos /= 2;)
s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
}
T query(int b, int e) { // query [b, e)
T ra = unit, rb = unit;
for (b += n, e += n; b < e; b /= 2, e /= 2) {
if (b % 2) ra = f(ra, s[b++]);
if (e % 2) rb = f(s[--e], rb);
}
return f(ra, rb);
}
};
//Fenwick Tree/BIT
struct BIT {
vector<ll> s;
BIT(int n) : s(n) {}
void update(int pos, ll dif) { // a[pos] += dif
for (; pos < sz(s); pos |= pos + 1) s[pos] += dif;
}
ll query(int pos) { // sum of values in [0, pos)
ll res = 0;
for (; pos > 0; pos &= pos - 1) res += s[pos-1];
return res;
}
int lower_bound(ll sum) {// min pos st sum of [0, pos] >= sum
// Returns n if no sum is >= sum, or -1 if empty sum is.
if (sum <= 0) return -1;
int pos = 0;
for (int pw = 1 << 25; pw; pw >>= 1) {
if (pos + pw <= sz(s) && s[pos + pw-1] < sum)
pos += pw, sum -= s[pos-1];
}
return pos;
}
};
void setIO(string s = "") {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// return; // for interactive problems
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("err.txt", "w", stderr);
freopen("out.txt", "w", stdout);
#else
if (sz(s)) {
freopen((s+".in").c_str(), "r", stdin);
freopen((s+".out").c_str(), "w", stdout);
}
#endif
}
db get_r(pdd &curr, db x) {
return (curr.f-x) * (curr.f-x)/(4*(curr.s));
}
void solve(int tc) {
int n; cin >> n;
V<db> ans(n);
stack<pdd> stk;
F0R(i, n) {
db x, r; cin >> x >> r;
db max_r = r;
while(!stk.empty()) {
pdd curr = stk.top();
db calc_r = get_r(curr, x);
ckmin(max_r, calc_r);
if (max_r >= curr.s) {
stk.pop();
} else {
break;
}
}
stk.push({x, max_r});
ans[i] = max_r;
}
each(x, ans) cout << fixed << setprecision(3) << x << '\n';
}
int main() {
setIO();
int t = 1;// cin >> t;
FOR(i, 1, t+1) solve(i);
cerr << "Time : " << (double)1000 * (double) clock() / CLOCKS_PER_SEC << "ms" << endl;
return 0;
}
Compilation message
bal.cpp: In function 'void setIO(std::string)':
bal.cpp:176:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
176 | freopen((s+".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bal.cpp:177:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
177 | freopen((s+".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
10 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
2 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
505 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
348 KB |
2000 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
1112 KB |
20000 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
2616 KB |
50000 numbers |
| 2 |
Correct |
30 ms |
2392 KB |
49912 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
67 ms |
4592 KB |
100000 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
80 ms |
5100 KB |
115362 numbers |
| 2 |
Correct |
79 ms |
5252 KB |
119971 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
106 ms |
6720 KB |
154271 numbers |
| 2 |
Correct |
118 ms |
8636 KB |
200000 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
127 ms |
7768 KB |
200000 numbers |
| 2 |
Correct |
149 ms |
8532 KB |
199945 numbers |
