oj.uz

Submission #483475

# Submission time Handle Problem Language Result Execution time Memory
483475 2021-10-29T19:59:30 Z Shin Balloons (CEOI11_bal) C++14
100 / 100
 130 ms 4988 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define all(x) x.begin(), x.end()

using namespace std;
const int N = 2e5 + 7;
const int MOD = 1e9 + 7; // 998244353;
const int INF = 1e9 + 7;
const long long INFLL = 1e18 + 7;

template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

#define SQR(x) 1.0 * (x) * (x)

int n;
pair<int, double> a[N];

void solve(void) {
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        int l, r; cin >> l >> r;
        a[i] = mp(l, r * 1.0);
    }

    stack<pair<int, double>> st;
    st.push(a[1]);
    for (int i = 2; i <= n; i ++) {
        while (!st.empty()) {
            pair<int, double> pre = st.top();
            minimize(a[i].se, SQR(pre.fi - a[i].fi) / (4.0 * pre.se));
            if (a[i].se < pre.se) break;
            st.pop();
        }
        st.push(a[i]);
    }

    for (int i = 1; i <= n; i ++) {
        cout << fixed << setprecision(3) << a[i].se << '\n';
    }
}

int main(void) {
    cin.tie(0)->sync_with_stdio(0); 
    int test = 1;
    // cin >> test;
    while (test --) {
        solve();
    }
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 800 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1612 KB 50000 numbers
2 Correct 38 ms 1332 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 2776 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 3200 KB 115362 numbers
2 Correct 65 ms 2884 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 4164 KB 154271 numbers
2 Correct 107 ms 4548 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 4988 KB 200000 numbers
2 Correct 107 ms 4576 KB 199945 numbers