oj.uz

Submission #211805

# Submission time Handle Problem Language Result Execution time Memory
211805 2020-03-21T10:43:18 Z MarcVana Balloons (CEOI11_bal) C++14
100 / 100
 904 ms 7316 KB 
#include <iostream>
#include <iomanip>
#include <stack>

#define x first
#define r second

using namespace std;

int N;
double X, R;

stack < pair <double, double> > S;

double balloon(double X, double R)
{
    while (!S.empty())
    {
        pair <double, double> p = S.top();
        R = min(R, (p.x - X) * (p.x - X) / (4.0 * p.r));
        if (R > p.r)
            S.pop();
        else
            break;
    }
    S.push({X, R});
    return R;
}

int main()
{
    cin >> N;
    for (int i = 1; i <= N; ++i)
    {
        cin >> X >> R;
        cout << fixed << setprecision(3) << balloon(X, R) << '\n';
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB 10 numbers

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB 2 numbers

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 256 KB 505 numbers

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 384 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 760 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 1748 KB 50000 numbers
2 Correct 235 ms 2084 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 2808 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 518 ms 3320 KB 115362 numbers
2 Correct 552 ms 4616 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 670 ms 4096 KB 154271 numbers
2 Correct 901 ms 7316 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 847 ms 4908 KB 200000 numbers
2 Correct 904 ms 7032 KB 199945 numbers