oj.uz

답안 #463879

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
463879 2021-08-11T23:48:22 Z training4usaco Balloons (CEOI11_bal) C++11
100 / 100
 239 ms 8524 KB 
#include <iostream>
#include <vector>
using namespace std;
#define MAXN 200000

int x[MAXN + 1], r[MAXN + 1], sta[MAXN + 1], st;
double ans[MAXN + 1];
int n;

int eps(double x) {  
    return x < -1e-10 ? -1 : x > 1e-10;
}
double sqr(double x) {
    return x * x;
}
void downdate(double &a, double b){  
    return (void)((eps(a - b) > 0) ? (a = b) : 0);
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> x[i] >> r[i];
    }
    ans[sta[st = 1] = 1] = r[1];
    for (int i = 2; i <= n; sta[++st] = i++) {
        for (ans[i] = r[i]; st && (downdate(ans[i], sqr(x[i] - x[sta[st]])/(4.0 * ans[sta[st]])), eps(ans[i] - ans[sta[st]]) >= 0); --st);
    }
    for (int i = 1; i <= n; ++i) {
        printf("%.3f\n", ans[i]);
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB 10 numbers

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB 2 numbers

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB 505 numbers

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 312 KB 2000 numbers

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 920 KB 20000 numbers

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 2256 KB 50000 numbers
2 Correct 57 ms 2324 KB 49912 numbers

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 4092 KB 100000 numbers

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 152 ms 4788 KB 115362 numbers
2 Correct 139 ms 5236 KB 119971 numbers

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 182 ms 6344 KB 154271 numbers
2 Correct 239 ms 8524 KB 200000 numbers

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 219 ms 7676 KB 200000 numbers
2 Correct 229 ms 8504 KB 199945 numbers