oj.uz

답안 #1017182

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1017182 2024-07-09T05:41:14 Z caterpillow Balloons (CEOI11_bal) C++17
100 / 100
 285 ms 11692 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
#define vt vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end() 
#define size(x) ((int) (x).size())
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'

template<template<typename> class Container, typename T>
ostream& operator<<(ostream& os, Container<T> o) {
    os << "{"; 
    int g = size(o); 
    for (auto i : o) os << i << ((--g) == 0 ? "" : ", "); 
    os << "}";
    return os;
}

void _print() {
    cerr << "\n";
}

template<typename T, typename ...V>
void _print(T t, V... v) {
    cerr << t; if (sizeof...(v)) cerr << ", "; _print(v...);
}

#ifdef LOCAL
#define dbg(x...) cerr << #x << " = "; _print(x);
#else
#define dbg(x...)
#define cerr if (0) std::cerr
#endif

using db = long double;
const db inf = 1e9;
const db eps = 1e-9;
const db maxr = 1e9;

struct Line {
    db m, c;

    db operator()(db x) {
        return m * x + c;
    }
    db inter(const Line& b) const {
        return (c - b.c) / (b.m - m);
    }
};

using ptr = struct Node*;
struct Node {
    Line line;
    ptr l, r;
};

db query(ptr n, db x, db l = 0, db r = maxr) {
    if (!n) return inf;
    db m = (r + l) / 2;
    if (x <= m) return min(query(n->l, x, l, m), n->line(x));
    else return min(n->line(x), query(n->r, x, m, r));
};

ptr ins(ptr n, Line cur, db l = 0, db r = maxr) {
    if (r - l < eps) return 0;
    if (!n) return new Node {cur, 0, 0};
    db m = (l + r) / 2;
    if (cur(m) < n->line(m)) swap(cur, n->line);
    bool lhs = cur(l) < n->line(l);
    bool rhs = cur(r) < n->line(r);
    if (lhs) n->l = ins(n->l, cur, l, m);
    if (rhs) n->r = ins(n->r, cur, m, r);
    return n;
}

main() {
    cin.tie(0)->sync_with_stdio(0);
    
    int n; cin >> n;
    using pd = pair<db, db>;
    vt<pd> pts(n);
    F0R (i, n) cin >> pts[i].f >> pts[i].s;
    ptr tree = 0;
    cout << fixed << setprecision(3);
    for (auto [x, maxr] : pts) {
        db rtrad = min(sqrtl(maxr), query(tree, x));
        cout << rtrad * rtrad << endl;
        db fact = (db) 1.0 / (2 * rtrad);
        tree = ins(tree, {fact, - x * fact});
    }
}

Compilation message

bal.cpp:85:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   85 | main() {
      | ^~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB 10 numbers

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB 2 numbers

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB 505 numbers

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 348 KB 2000 numbers

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 1616 KB 20000 numbers

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 2896 KB 50000 numbers
2 Correct 57 ms 3156 KB 49912 numbers

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 118 ms 5044 KB 100000 numbers

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 146 ms 5712 KB 115362 numbers
2 Correct 117 ms 7252 KB 119971 numbers

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 170 ms 7248 KB 154271 numbers
2 Correct 205 ms 11692 KB 200000 numbers

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 285 ms 11092 KB 200000 numbers
2 Correct 187 ms 11604 KB 199945 numbers