Submission #1038286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038286		i_liek_cheezits	Balloons (CEOI11_bal)	C++17	100 / 100	149 ms	8636 KiB

bal

#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 (stderr)

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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10