oj.uz

Submission #638725

# Submission time Handle Problem Language Result Execution time Memory
638725 2022-09-07T07:19:22 Z m15069 Balloons (CEOI11_bal) C++17
100 / 100
 494 ms 5624 KB 
#include<bits/stdc++.h>
using namespace std; 
using ll = long long; 
#define IO ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0);

// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp> 
// using namespace __gnu_pbds; 
// #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
const int N = 5e7 + 10;
int tc; 

long double r2(pair<ll,long double>a, pair<ll,long double>b)
  {
    return (a.first - b.first) * (a.first - b.first) / (4.0 * (a.second));
  }

void solve()
{

  long long n; cin >> n; 
  stack<pair<ll,long double>>st; 
  for(int i = 0 ; i < n; i++)
  {
    long long x,r; cin >> x >> r; 
    long double best_ans = r; 
    while(!st.empty())
    {
        long double temp = r2(st.top(), {x,best_ans});
        best_ans = min(temp,best_ans);
        // when to pop? 
        if(best_ans >= st.top().second)st.pop(); 
        else break;
        // cout << i << " " <<  best_ans << '\n';
    }
    st.push({x,best_ans}); // best redius 
    cout << fixed << setprecision(4)<< best_ans << '\n';
  }

}


int main()
{
    // freopen("path.in", "r", stdin);
    // IO
    int t = 1; 
    // get prime numbers using sieve 
    // cin >> t; 
    while(t--)
        {tc++;
          solve(); 
        }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 212 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 412 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 1076 KB 50000 numbers
2 Correct 125 ms 1592 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 1532 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 1704 KB 115362 numbers
2 Correct 293 ms 3404 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 374 ms 1996 KB 154271 numbers
2 Correct 494 ms 5624 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 2216 KB 200000 numbers
2 Correct 475 ms 5580 KB 199945 numbers