oj.uz

Submission #657007

# Submission time Handle Problem Language Result Execution time Memory
657007 2022-11-08T17:32:57 Z Nafeeszx Balloons (CEOI11_bal) C++14
100 / 100
 187 ms 10136 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define trav(a, x) for(auto& a : x)
#define FOR(i, a, b) for (int i=(a); i<=(signed)(b); i++)
#define ROF(i, a, b) for (int i=(a); i>=(signed)(b); i--)
#define F0R(i, a) for (int i=0; i<(signed)(a); i++)
#define vi vector<int>
#define all(v) (v).begin(), (v).end()
#define f first
#define s second
typedef long long ll;

const int mod = 1e9 + 7, MOD = 998244353;

int main()
{	
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    vector<pair<double, double>> v(n);
    stack<pair<double, double>> rad;
    vector<double> res(n);
    F0R(i, n) {
        cin >> v[i].first >> v[i].second;
    }
    F0R(i, n) {
        
        double ans = v[i].second;
            
        while(!rad.empty()) {
            ans = min(ans, ((rad.top().first - v[i].first)*(rad.top().first - v[i].first))/(4*rad.top().second));           
            if(ans >= rad.top().second) rad.pop();
            else break;
        } 
                    
        res[i] = min(ans, v[i].second);
        rad.push({v[i].first, res[i]});
    
    }
    F0R(i, n) {
        cout << fixed << setprecision(3) << res[i] << "\n";
    }

    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 884 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 2008 KB 50000 numbers
2 Correct 48 ms 2736 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 3572 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 4192 KB 115362 numbers
2 Correct 107 ms 6192 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 5340 KB 154271 numbers
2 Correct 182 ms 10136 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 6584 KB 200000 numbers
2 Correct 178 ms 10048 KB 199945 numbers