oj.uz

Submission #151750

# Submission time Handle Problem Language Result Execution time Memory
151750 2019-09-04T14:33:08 Z forestryks Balloons (CEOI11_bal) C++14
100 / 100
 329 ms 16636 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
#define rep(i, n) for (int (i) = 0; (i) < (n); ++(i))
#define all(x) (x).begin(), (x).end()
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define f first
#define s second

const int MAXN = 2e5 + 5;
int n;
pair<ld, ld> a[MAXN];

ld get(ld x1, ld r1, ld x) {
    return (x1 - x) * (x1 - x) / 4 / r1;
}

int main() {
    FAST_IO;
    cout.precision(10);
    cout.setf(ios::fixed);

    cin >> n;
    rep(i, n) {
        cin >> a[i].f >> a[i].s;
    }

    vector<pair<ld, ld>> st;
    rep(i, n) {
        while (!st.empty()) {
            a[i].s = min(a[i].s, get(st.back().f, st.back().s, a[i].f));
            if (a[i].s > st.back().s) st.pop_back();
            else break;
        }

        st.push_back(a[i]);
        cout << a[i].s << '\n';
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1528 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 3924 KB 50000 numbers
2 Correct 75 ms 4532 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 6920 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 7988 KB 115362 numbers
2 Correct 164 ms 10092 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 10232 KB 154271 numbers
2 Correct 275 ms 16636 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 12696 KB 200000 numbers
2 Correct 267 ms 16492 KB 199945 numbers