oj.uz

Submission #467592

# Submission time Handle Problem Language Result Execution time Memory
467592 2021-08-23T18:40:13 Z nicolaalexandra Balloons (CEOI11_bal) C++14
100 / 100
 352 ms 12112 KB 
#include <bits/stdc++.h>
#define DIM 200010
using namespace std;

struct cerc{
    long long x;
    long double r;
} v[DIM];

int n,i,j;
deque <int> d;

long double get_raza (int i, int j){

    v[i].r = min (v[i].r, 1.0 * (v[i].x - v[j].x) * (v[i].x - v[j].x) / (4.0 * v[j].r));
    return v[i].r;
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n;
    for (i=1;i<=n;i++)
        cin>>v[i].x>>v[i].r;

    for (i=1;i<=n;i++){


        while (!d.empty() && get_raza(i,d.back()) > v[d.back()].r)
            d.pop_back();
        d.push_back(i);

        cout<<setprecision(3)<<fixed<<v[i].r<<"\n";
    }


    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 332 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1224 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 3004 KB 50000 numbers
2 Correct 88 ms 3188 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 5444 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 6076 KB 115362 numbers
2 Correct 247 ms 7280 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 7628 KB 154271 numbers
2 Correct 349 ms 12060 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 9160 KB 200000 numbers
2 Correct 352 ms 12112 KB 199945 numbers