Submission #1017175

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1017175	2024-07-09T05:38:27 Z	caterpillow	Balloons (CEOI11_bal)	C++17	30 / 100	272 ms	10832 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 mxr = 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 = mxr) {
    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 = mxr) {
    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;
}


/*

cht

*/

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;
    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:92:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   92 | main() {
      | ^~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	348 KB	1st numbers differ - expected: '247294217.0000000000', found: '247294000.0000000000', error = '217.0000000000'
2	Halted	0 ms	0 KB	-

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
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	35 ms	1564 KB	2953rd numbers differ - expected: '1030.4380000000', found: '1030.4400000000', error = '0.0020000000'
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	58 ms	2900 KB	251st numbers differ - expected: '15123.0020000000', found: '15123.0000000000', error = '0.0020000000'
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	115 ms	4692 KB	285th numbers differ - expected: '7629.0020000000', found: '7629.0000000000', error = '0.0020000000'
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	130 ms	5312 KB	511th numbers differ - expected: '4494.0050000000', found: '4494.0100000000', error = '0.0050000000'
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	180 ms	6736 KB	164th numbers differ - expected: '1698.0020000000', found: '1698.0000000000', error = '0.0020000000'
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	272 ms	10832 KB	248th numbers differ - expected: '2694.0020000000', found: '2694.0000000000', error = '0.0020000000'
2	Halted	0 ms	0 KB	-