| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 651064 |
2022-10-16T19:58:30 Z |
Samrev |
Balloons (CEOI11_bal) |
C++14 |
|
164 ms |
11688 KB |
#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){
break;
}
else{
radius.pop();
}
}
cout << fixed <<setprecision(3);
cout<<br[i].second<<"\n";
radius.push(br[i]);
}
}
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
10 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
2 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
505 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
2000 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
1032 KB |
20000 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
2600 KB |
50000 numbers |
| 2 |
Correct |
42 ms |
3144 KB |
49912 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
4540 KB |
100000 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
105 ms |
5360 KB |
115362 numbers |
| 2 |
Correct |
101 ms |
7172 KB |
119971 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
136 ms |
6732 KB |
154271 numbers |
| 2 |
Correct |
159 ms |
11688 KB |
200000 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
164 ms |
8168 KB |
200000 numbers |
| 2 |
Correct |
153 ms |
11636 KB |
199945 numbers |
