/* Gaurav Arora */
//******************************************************TEMPLATE START******************************************************************
#include <bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// template <typename num_t>
// using ordered_set = tree<num_t, null_type, less_equal<num_t>, rb_tree_tag, tree_order_statistics_node_update>;
using namespace chrono;
#define gc getchar_unlocked
#define inf INT_MAX
#define minf INT_MIN
#define ff first
#define ss second
#define mp make_pair
#define nline "\n"
#define pb push_back
#define sz(x) ((int)(x).size())
#define len(x) ((int)(x).length())
#define all(x) x.begin(), x.end()
#define sortall(x) sort(all(x))
#define PI 3.1415926535897932384626
#define msb(x) (31 - __builtin_clz(x))
#define msbll(x) (63 - __builtin_clzll(x))
#define NoSetbitsll(x) __builtin_popcountll(x)
#define setminus(x) memset(x, -1, sizeof(x))
#define setzero(x) memset(x, 0, sizeof(x))
#define f(i, n) for (i = 0; i < n; i++)
#define fe(i,n) for (i = 1; i <=n; i++)
#define fos(i, s, n, k) for (i = s; i < n; i = i + k)
#define fom(i, s, n, k) for (i = s; i < n; i = i * k)
#define uniq(x) (x).erase(unique(all(x)), (x).end())
#define getunique(v) {sort(all(v)); v.erase(unique(all(v)), v.end());} // for Vector v
#define printPrecision(p, Value) cout << fixed << setprecision(p) << Value
#define tr(it, a) for (auto it = a.begin(); it != a.end(); it++)
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<vpi> vvpi;
typedef vector<vpl> vvpl;
typedef vector<bool> vb;
#ifndef ONLINE_JUDGE
#define deb(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define deb(x)
#endif
#pragma warning disable format
//Debugger
void _print(ll t) { cerr << t; }
void _print(int t) { cerr << t; }
void _print(string t) { cerr << t; }
void _print(char t) { cerr << t; }
void _print(lld t) { cerr << t; }
void _print(double t) { cerr << t; }
void _print(ull t) { cerr << t; }
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) { cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}"; }
template <class T> void _print(vector <T> v) { cerr << "[ "; for (T i : v) { _print(i); cerr << " "; } cerr << "]"; }
template <class T> void _print(set <T> v) { cerr << "[ "; for (T i : v) { _print(i); cerr << " "; } cerr << "]"; }
template <class T> void _print(deque <T> v) { cerr << "[ "; for (T i : v) { _print(i); cerr << " "; } cerr << "]"; }
template <class T> void _print(multiset <T> v) { cerr << "[ "; for (T i : v) { _print(i); cerr << " "; } cerr << "]"; }
template <class T, class V> void _print(map <T, V> v) { cerr << "[ "; for (auto i : v) { _print(i); cerr << " "; } cerr << "]"; }
// template <class T> void _print(ordered_set<T> v) { cerr << "[ "; for (auto i : v) { _print(i); cerr << " "; } cerr << "]"; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll getRandomNumber(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); }
ll gcd(ll a, ll b) { if (b > a) { return gcd(b, a); } if (b == 0) { return a; } return gcd(b, a % b); }
ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }
ll powm(ll a, ll b, ll mod) { ll res = 1; while (b > 0) { if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1; } return res; } //power modulo m
void extendgcd(ll a, ll b, ll* v) { if (b == 0) { v[0] = 1; v[1] = 0; v[2] = a; return; } extendgcd(b, a % b, v); ll x = v[1]; v[1] = v[0] - v[1] * (a / b); v[0] = x; return; } //pass an array of size 3
ll mminv(ll a, ll b) { ll arr[3]; extendgcd(a, b, arr); return arr[0]; } //for non prime b
ll mminvprime(ll a, ll b) { if (a % b == 0) return -1; return powm(a, b - 2, b); } //for prime only
vector<ll> sieve(int n) { int* arr = new int[n + 1](); vector<ll> vect; for (int i = 2; i <= n; i++)if (arr[i] == 0) { vect.push_back(i); for (int j = i * i; j <= n; j += i)arr[j] = 1; } return vect; }
vector<string> split(string s, char delimeter) { vector <string> tokens; stringstream check1(s); string intermediate; while (getline(check1, intermediate, delimeter)) { tokens.push_back(intermediate); } return tokens; }
string stringRemZeroes(string s) { string res; bool flag = true; for (int i = 0;i < s.length();i++) { if (s[i] == '0' && flag) continue; else { flag = false; res.push_back(s[i]); } } if (res.size() == 0) res = "0"; return res; }
void toLower(string& s) { transform(s.begin(), s.end(), s.begin(), ::tolower); }
void toUpper(string& s) { transform(s.begin(), s.end(), s.begin(), ::toupper); }
ll stringToNo(string s) { stringstream din(s); ll x; din >> x; return x; }
ll addm(ll a, ll b, ll m) { a = a % m; b = b % m; return (((a + b) % m) + m) % m; }
ll mulm(ll a, ll b, ll m) { a = a % m; b = b % m; return (((a * b) % m) + m) % m; }
ll subm(ll a, ll b, ll m) { a = a % m; b = b % m; return (((a - b) % m) + m) % m; }
ll divm(ll a, ll b, ll m) { a = a % m; b = b % m; return (mulm(a, mminvprime(b, m), m) + m) % m; } //only for prime m
const ll SIZE = 2; // change size before calling
ll fact[SIZE], ifact[SIZE];
void gen_factorial(ll n, ll mod) { fact[0] = fact[1] = ifact[0] = ifact[1] = 1; for (ll i = 2; i <= n; i++) { fact[i] = (i * fact[i - 1]) % mod; } ifact[n] = mminvprime(fact[n], mod); for (ll i = n - 1; i >= 2; i--) { ifact[i] = ((i + 1) * ifact[i + 1]) % mod; } }
ll choose(ll n, ll r, ll m) { ll val1 = fact[n]; ll val2 = ifact[n - r]; ll val3 = ifact[r]; return (((val1 * val2) % m) * val3) % m; } //First make fact and ifact for this to work both ll
//Range intersection
pl intersection(pl a, pl b) { if (a.first > b.second || a.second < b.first) { return mp(-inf, -inf); } else { b.first = max(b.first, a.first); b.second = min(b.second, a.second); } return b; }
pl findRatio(ll a, ll b) { ll g = gcd(a, b); a /= g; b /= g; return mp(a, b); }
template <typename T> void amax(T& a, T b) { a = max(a, b); }
template <typename T> void amin(T& a, T b) { a = min(a, b); }
const int MOD1 = 1000000007;
const int MOD2 = 998244353;
#pragma warning restore format
//**********************************************************TEMPLATE ENDS****************************************************************
/*
THINGS TO KEEP IN MIND BEFORE SUBMITTTING
* Always Check Which MOD it is Asking For
* Unique function return iterator Then We can resize the container
* Look for Possible Edge Cases
* int overflows, array bounds, etc.
* https://oeis.org/ Sequence Related Problem
* a+b=a|b+a&b
* a+b=a^b+2*(a&b)
* DO NOT GET STUCK ON ONE APPROACH
* DO NOT GET STUCK ON ONE APPROACH
* DO NOT GET STUCK ON ONE APPROACH
*/
#define int long long
int i, j, k;
int n, m;
vector<int> previousSmaller(vector<int>& values)
{
int n = values.size();
vector<int> ps(n);
stack<int> st;
for (int i = 0;i < n;i++)
{
while ((!st.empty()) && (values[st.top()] >= values[i]))
st.pop();
ps[i] = (st.empty()) ? -1 : st.top();
st.push(i);
}
return ps;
}
vector<int> nextSmaller(vector<int>& values)
{
int n = values.size();
vector<int> ns(n);
stack<int> st;
for (i = n - 1;i >= 0;i--)
{
while ((!st.empty()) && (values[st.top()] >= values[i]))
st.pop();
ns[i] = (st.empty()) ? n : st.top();
st.push(i);
}
return ns;
}
void solve()
{
int n;
cin >> n;
vector<int> pos(n);
vector<double> radius(n);
for (int i = 0;i < n;i++)
cin >> pos[i] >> radius[i];
vector<double> maxAllowedRadius(n);
stack<pair<int, double>> st;
for (int i = 0;i < n;i++)
{
double maxRadius = radius[i];
while (!st.empty())
{
pair<int, double> top = st.top();
amin(maxRadius, ((double((top.first - pos[i]) * (top.first - pos[i]))) / (4 * top.second)));
if (st.top().second <= maxRadius)
st.pop();
else break;
}
st.push({ pos[i],maxRadius });
maxAllowedRadius[i] = maxRadius;
cout << maxRadius << " ";
}
cout << nline;
}
signed main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cout << fixed << setprecision(3);
int t = 1;
// cin >> t;
int count = 1;
while (t--) {
// cout << "Case #" << count << ": ";
count++;
solve();
}
return 0;
}
Compilation message
bal.cpp:57: warning: ignoring '#pragma warning disable' [-Wunknown-pragmas]
57 | #pragma warning disable format
|
bal.cpp:111: warning: ignoring '#pragma warning restore' [-Wunknown-pragmas]
111 | #pragma warning restore format
|
bal.cpp: In function 'std::string stringRemZeroes(std::string)':
bal.cpp:92:83: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | string stringRemZeroes(string s) { string res; bool flag = true; for (int i = 0;i < s.length();i++) { if (s[i] == '0' && flag) continue; else { flag = false; res.push_back(s[i]); } } if (res.size() == 0) res = "0"; return res; }
| ~~^~~~~~~~~~~~
bal.cpp: In function 'void gen_factorial(ll, ll)':
bal.cpp:102:117: warning: array subscript 2 is above array bounds of 'll [2]' {aka 'long long int [2]'} [-Warray-bounds]
102 | void gen_factorial(ll n, ll mod) { fact[0] = fact[1] = ifact[0] = ifact[1] = 1; for (ll i = 2; i <= n; i++) { fact[i] = (i * fact[i - 1]) % mod; } ifact[n] = mminvprime(fact[n], mod); for (ll i = n - 1; i >= 2; i--) { ifact[i] = ((i + 1) * ifact[i + 1]) % mod; } }
| ~~~~~~^
bal.cpp:101:4: note: while referencing 'fact'
101 | ll fact[SIZE], ifact[SIZE];
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
10 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
2 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
505 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
2000 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
912 KB |
20000 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
2004 KB |
50000 numbers |
| 2 |
Correct |
39 ms |
2712 KB |
49912 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
98 ms |
3684 KB |
100000 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
112 ms |
4160 KB |
115362 numbers |
| 2 |
Correct |
90 ms |
6168 KB |
119971 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
130 ms |
5428 KB |
154271 numbers |
| 2 |
Correct |
155 ms |
10096 KB |
200000 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
158 ms |
6676 KB |
200000 numbers |
| 2 |
Correct |
165 ms |
10224 KB |
199945 numbers |
