oj.uz

Submission #685748

# Submission time Handle Problem Language Result Execution time Memory
685748 2023-01-25T00:15:42 Z Magikarp4000 Balloons (CEOI11_bal) C++17
100 / 100
 187 ms 6552 KB 
#include <bits/stdc++.h>
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int(1e9+7)
#define ln '\n' 
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define in(v,x) (v.find(x) != v.end())
#define F first
#define S second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 1e18+1;

const int MAXN = 2e5+1;
int n;
double x[MAXN], r[MAXN], a[MAXN];

double susify(int p, int q) {
    return ((x[p]-x[q])*(x[p]-x[q]))/(4*a[q]);
}

signed main() {
    OPTM;
    cin >> n;
    FOR(i,0,n) cin >> x[i] >> r[i];
    stack<int> st;
    a[0] = r[0];
    st.push(0);
    FOR(i,1,n) {
        a[i] = r[i];
        if (a[i] < a[i-1]) {
            a[i] = min(a[i], susify(i,i-1));
            st.push(i);
        }
        else {
            while (!st.empty()) {
                int cur = st.top();
                a[i] = min(a[i], susify(i,cur));
                if (a[cur] > a[i]) break;
                st.pop();
            }
            st.push(i);
        }
    }
    FOR(i,0,n) cout << fixed << setprecision(3) << a[i] << ln;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 980 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 1912 KB 50000 numbers
2 Correct 46 ms 1772 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 3532 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 4084 KB 115362 numbers
2 Correct 121 ms 3796 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 5320 KB 154271 numbers
2 Correct 175 ms 6220 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 6552 KB 200000 numbers
2 Correct 184 ms 6104 KB 199945 numbers