Submission #869272

#	Time	Username	Problem	Language	Result	Execution time	Memory
869272		tvladm2009	Balloons (CEOI11_bal)	C++17	100 / 100	176 ms	13248 KiB

bal

#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <cassert>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <numeric>

using namespace std;

typedef long long ll;
typedef long double ld;
const int N = (int)2e5 + 7;
ld x[N], r[N];
int n;

struct Circle {
        ld x;
        ld y;
        ld radius;
};

bool check(Circle a, Circle b) {
        if (4 * a.x * b.x >= (a.y - b.y) * (a.y - b.y)) {
                return false;
        }
        return true;
}

int main() {
#ifndef ONPC
        ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#else
        FILE* stream;
        freopen("input.txt", "r", stdin);
#endif
        cin >> n;
        for (int i = 1; i <= n; i++) {
                cin >> x[i] >> r[i];
        }
        vector<pair<ld, ld>> stk;
        for (int i = 1; i <= n; i++) {
                ld cur = r[i];
                while (!stk.empty()) {
                        ld dist = x[i] - stk.back().second;
                        cur = min(cur, dist * dist / (4 * stk.back().first));
                        if (stk.back().first <= cur) {
                                stk.pop_back();
                        }
                        else {
                                break;
                        }
                }
                cout << setprecision(10) << fixed << cur << "\n";
                stk.push_back({cur, x[i]});
        }
        return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10