oj.uz

Submission #634839

# Submission time Handle Problem Language Result Execution time Memory
634839 2022-08-25T06:26:44 Z SharpEdged Balloons (CEOI11_bal) C++17
100 / 100
 325 ms 11892 KB 
/* Online C++ Compiler and Editor */
#include <bits/stdc++.h>

#define f first
#define s second

typedef long double ld;

using namespace std;

int main()
{
   int n; cin >> n;
   vector<ld> x(n); vector<ld> r(n);
   stack<pair<ld, ld>> mono;
   auto eval = [&](pair<ld, ld> prev, ld x) -> ld {
       return (prev.f - x) * (prev.f - x) / (4 * prev.s);
   };
   for (int i = 0; i < n; i++){
       cin >> x[i] >> r[i];
       while (!mono.empty()){
           ld val = eval(mono.top(), x[i]);
           r[i] = min(r[i], val);
           if (mono.top().s <= r[i]) {
               mono.pop();
           } else {
               break;
           }
       }
       mono.push({x[i], r[i]});
   }
   cout << fixed << setprecision(4) << '\n';
   for (int i = 0; i < n; i++) cout << r[i] << '\n';
   return 0;
}

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 1 ms 212 KB 505 numbers

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1088 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 2672 KB 50000 numbers
2 Correct 95 ms 2256 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 4616 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 5352 KB 115362 numbers
2 Correct 197 ms 7296 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 6764 KB 154271 numbers
2 Correct 323 ms 11864 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 8384 KB 200000 numbers
2 Correct 325 ms 11892 KB 199945 numbers