Submission #651063

#	Time	Username	Problem	Language	Result	Execution time	Memory
651063		Samrev	Balloons (CEOI11_bal)	C++14	10 / 100	162 ms	8376 KiB

bal

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef long double lld;
typedef priority_queue <lli , vector<lli>, greater<lli> > min_heap;
typedef priority_queue <lli> max_heap;
typedef pair<lli, lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;

const lli  M = 1e9 + 7;
const lli M1 = 0;
const lli M2 = 1000000000000000001;
lli mod(lli x){   return (x%M);}
lli mod_minus(lli a, lli b){ lli ans= (mod(a)-mod(b)); if(ans<0) ans=mod(ans+M); return ans;}
lli mod_mul(lli a,lli b){  return mod(mod(a)*mod(b));}
lli mod_add(lli a,lli b){ return mod(mod(a)+mod(b));}
#define FOR(i,l,u) for(int i=l;i<=u;i++)
#define FAST ios_base :: sync_with_stdio (false); cin.tie (NULL)
#define All(A) A.begin(),A.end()
#define isPowerOfTwo(x) (x && (!(x&(x-1))))
#define LSOne(S) (S & (-S))
#define set_count(i)  __builtin_popcount(i)
lli gcd(lli a, lli b) { return b == 0 ? a : gcd(b, a % b); }
lli lcm(lli a, lli b) { return a * (b / gcd(a, b)); }
lli phi(lli n) {
    lli result = n;
    for (lli i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            while (n % i == 0)
                n /= i;
            result -= result / i;
        }
    }
    if (n > 1)
        result -= result / n;
    return result;
}

lli ceill(lli a,lli b)
{
    if(a%b==0)
        return a/b;
    else
        return a/b +1;
}

lli extendted_gcd(lli a ,lli b,lli &x,lli &y){
    if(a==0){
        x=0;y=1;return b;}
        lli x1,y1,ans = extendted_gcd(b%a,a,x1,y1);
        x = y1-(b/a)*x1;y = x1;
        return ans;
    }
lli power_mod(lli a,lli b,lli m)
{
    lli ans =1;
    while(b!=0)
    {
        if(b%2==1)
            ans=(ans*a)%m;
        a=a*a;
        a%=m;
        b/=2;
    }
    return ans;
}
lli mod_inverse(lli a,lli m)
{
    return power_mod(a,m-2,m);
}
void mod_inverse_array(lli inv[],lli u,lli m)
{
    inv[1]=1;
    FOR(i,2,u){
        inv[i]=((-(m/i)*inv[m%i]%m)+m)%m;
    }
}
lli N_C_r_mod_m(lli N,lli r , vector<lli> factorial)
{
    lli a = factorial[N],b = mod_inverse(factorial[N-r],M),c = mod_inverse(factorial[r],M);
    return mod_mul(a,mod_mul(b,c));
}
void prime_factorization(lli n,unordered_map<lli,lli> &m)
{
    lli i=2;
    while(n%i==0)
    {
        m[i]++;
        n=n/i;
    }
    for(i=3;i*i<=n;i+=2)
    {
        while(n%i==0)
        {
            m[i]++;
            n=n/i;
        }
    }
    if(n!=1)   
        m[n]++;
}

void linear_sieve(vector<lli> &pr,vector<lli> &lp,lli N)
{
    for (lli i=2; i<=N; ++i) {
        if (lp[i] == 0) {
            lp[i] = i;
            pr.push_back (i);
        }

        for (lli j=0; j<(lli)pr.size() && pr[j]<=lp[i] && i*pr[j]<=N; ++j)
            lp[i * pr[j]] = pr[j];

    }


}

lli eval_poly(vector<lli> coeff , lli x){
    lli degree = coeff.size(); //coeff are as 0,1,2----n
    degree--;
    lli ans = 0;
    for(lli i = degree ; i>=0 ; i--){
        ans = (x*ans + coeff[i]);
    }
    return ans;
}

lli derivative_poly(vector<lli> coeff , lli x){
    lli degree = coeff.size(); //coeff are as 0,1,2----n
    degree--;
    lli ans = 0;
    lli pow = 1;
    for(lli i = 1; i<=degree;i++){
        ans+=(i*pow*coeff[i]);
        pow*=x;
    }
    return ans;

}

int t = 1;
lli T(lli H, lli W){
    lli a =  mod_mul(mod_mul(H , H+1), mod_inverse(2,M));
    lli b =  mod_mul(mod_mul(W , W+1), mod_inverse(2,M));

    return mod_mul(a,b);
}
lli sol(vector<lli> h , vector<lli> w){
    lli ans = 0;
    lli n = h.size();
    lli W = 0;
    for(lli i = 0 ; i<(n-1); i++){
        W += w[i];
        ans = mod_add(ans ,  T(h[i],W));
        ans = mod_minus(ans , T(h[i+1],W));
        // cout<<ans<<"\n";
    }
    return ans;
}
lld cal(lld a,lli x1 , lli x2 ){
    return (x2-x1)*(x2-x1)/(4*a);
}
void solve(){
    
    int n ; cin>>n;
    vector<pair<lli,lld>> br(n);
    FOR(i,0,n-1){
        cin>>br[i].first>>br[i].second;
    }

    stack<pair<lli,lld>> radius;
    radius.push(br[0]);
    cout << fixed <<setprecision(3);
    cout<<br[0].second<<"\n";
    FOR(i,1,n-1){
        while(!radius.empty()){
            br[i].second = min(br[i].second, cal(radius.top().second,radius.top().first,br[i].first));
            if(br[i].second < radius.top().second){
                radius.push(br[i]);
                break;
            }
            else{
                radius.pop();
            }
        }
        //cout << fixed <<setprecision(3);
        cout<<br[i].second<<"\n";
    }

}
int main()
{

    FAST;
    // #ifndef ONLINE_JUDGE
    //     freopen("input.txt", "r", stdin);
    //     freopen("output.txt", "w", stderr);
    //     freopen("output.txt", "w", stdout);
    // #endif
    // g++ -o output prac.cpp
    // .\output
    // cin>>t;
    // cout<<__builtin_clz(2)<<"\n";
    solve();
    return 0;

}

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