Submission #1017182

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
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

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	348 KB	2000 numbers

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	1616 KB	20000 numbers

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	56 ms	2896 KB	50000 numbers
2	Correct	57 ms	3156 KB	49912 numbers

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	118 ms	5044 KB	100000 numbers

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	146 ms	5712 KB	115362 numbers
2	Correct	117 ms	7252 KB	119971 numbers

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	170 ms	7248 KB	154271 numbers
2	Correct	205 ms	11692 KB	200000 numbers

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	285 ms	11092 KB	200000 numbers
2	Correct	187 ms	11604 KB	199945 numbers