oj.uz

Submission #872488

# Submission time Handle Problem Language Result Execution time Memory
872488 2023-11-13T07:56:29 Z sleepntsheep Balloons (CEOI11_bal) C++17
100 / 100
 156 ms 9296 KB 
#include <iostream>
#include <cassert>
#include <iomanip> 
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>

using i64 = long long;
using u64 = unsigned long long;
using f80 = long double;

using namespace std;
#define ALL(x) x.begin(), x.end()
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
#define N 200005


int n, x[N];
f80 r[N];

struct Line {
	mutable f80 k, m, p;
	bool operator<(const Line& o) const { return k < o.k; }
	bool operator<(i64 x) const { return p < x; }
};

struct LineContainer : multiset<Line, less<>> {
	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
	const f80 inf = f80(1)/0;
    f80 div(f80 a, f80 b) { return a/b;}
	bool isect(iterator x, iterator y) {
		if (y == end()) return x->p = inf, 0;
		if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
		else x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}
	void add(f80 k, f80 m) {
		auto z = insert({k, m, 0}), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p)
			isect(x, erase(y));
	}
	f80 query(i64 x) {
		assert(!empty());
		auto l = *lower_bound(x);
		return l.k * x + l.m;
	}
} lc;


int main()
{
    ShinLena;
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> x[i] >> r[i];

    f80 twoa = 2L * sqrtl(r[0]);
    lc.add(-1 / twoa, x[0] / twoa);

    for (int i = 1; i < n; ++i)
    {
        f80 j = lc.query(x[i]);
        r[i] = min(r[i], j * j);

        f80 twoa = 2L * sqrtl(r[i]);
        lc.add(-1 / twoa, x[i] / twoa);
    }

    cout << fixed << setprecision(3);
    for (int i = 0; i < n; ++i)
        cout << r[i] << '\n';

    return 0;
}

Compilation message

bal.cpp:34:24: warning: division by zero [-Wdiv-by-zero]
   34 |  const f80 inf = f80(1)/0;
      |                  ~~~~~~^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 344 KB 505 numbers

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2788 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 3296 KB 50000 numbers
2 Correct 36 ms 4188 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 3924 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 3920 KB 115362 numbers
2 Correct 83 ms 6100 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 4692 KB 154271 numbers
2 Correct 143 ms 9296 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 5856 KB 200000 numbers
2 Correct 141 ms 5700 KB 199945 numbers