| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1078560 |
2024-08-27T20:59:13 Z |
BoggyMan |
Balloons (CEOI11_bal) |
C++14 |
|
123 ms |
10128 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<int, int> pip;
typedef pair<ll, ll> plip;
typedef vector<int> vi;
typedef vector<ll> vli;
typedef vector<vi> vvi;
typedef vector<vli> vvli;
typedef vector<pip> vpip;
typedef unordered_set<ll> usi;
typedef set<ll> si;
typedef priority_queue<ll> pq;
typedef unordered_map<ll, ll> umpi;
typedef map<ll, ll> mpi;
typedef long long int ll;
#define mod 1000000007
#define nl "\n"
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define Rep(i, n) for (int i = 0; i < (n); i++)
#define ALL(v) (v).begin(), (v).end()
#define Be(v) (v).begin()
#define Ee(v) (v).end()
#define Pb push_back
#define Mp make_pair
#define Sz(v) ((int)(v).size())
#define F first
#define S second
#define pr(v) cout<<v<<endl;
const int MOD = 1000000007;
// void file() {
// #ifndef ONLINE_JUDGE
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// #endif
// }
//
class SegmentTree {
ll *seg;
ll *lazy;
public :
SegmentTree(ll n) {
// Maximum Size Of Tree could be 4n only
seg = new ll[4*n + 1];
lazy = new ll[4*n + 1];
}
// Time Complexity Of Build : O(4N) == O(N) !!!
void BuildTree(ll arr[], ll i, ll low, ll high) {
if(low == high) {
seg[i] = arr[low];
return;
}
ll mid = low + (high - low) / 2;
// Left Child
BuildTree(arr, 2 * i + 1, low, mid);
// Right Child
BuildTree(arr, 2 * i + 2, mid + 1, high);
// Sum Of Two
seg[i] = seg[2 * i + 1] + seg[2 * i + 2];
}
// Query Time Complexity : O(logN)
ll query(ll ind, ll l, ll r, ll low, ll high) {
// If Update is Remaining, First Update The Values
if(lazy[ind] != 0) {
seg[ind] += (high - low + 1) * lazy[ind];
// If it is a leaf node, it will not have childrens
if(low != high) {
lazy[2 * ind + 1] += lazy[ind];
lazy[2 * ind + 2] += lazy[ind];
}
lazy[ind] = 0;
}
// No Overlap
// l r low high or low high l r
if(high < l || low > r) return 0;
// Complete Overlap
// l low high r
if(high <= r && low >= l) return seg[ind];
// Partial Overlap
ll mid = low + (high - low) / 2;
ll left = query(2 * ind + 1, l, r, low, mid);
ll right = query(2 * ind + 2, l, r, mid + 1, high);
return left + right;
}
// Update Time Complexity : O(logN)
void update(ll i, ll val, ll low, ll high, ll ind) {
// If we found the required Node
if(low == high) {
seg[ind] = val;
return;
}
ll mid = low + (high - low)/2;
// If required node is left to mid,
// Move To Left Child Else Move To Right Child
if(i <= mid) update(i, val, low, mid, 2 * ind + 1);
else update(i, val, mid + 1, high, 2 * ind + 2);
// Since, One Of The Child's Value is Updated
// We have to find minimum again !!!
seg[ind] = seg[2 * ind + 1] + seg[2 * ind + 2];
}
void updateRange(ll l, ll r, ll val, ll low, ll high, ll ind) {
// First Update The Remaining Updates
// Lazy Propagate To The Child
if(lazy[ind] != 0) {
seg[ind] += (high - low + 1) * lazy[ind];
// If it is a leaf node, it will not have childrens
if(low != high) {
lazy[2 * ind + 1] += lazy[ind];
lazy[2 * ind + 2] += lazy[ind];
}
lazy[ind] = 0;
}
// No Overlap
// l r low high or low high l r
if(high < l || low > r) return;
// Complete Overlap
// l low high r
if(high <= r && low >= l) {
seg[ind] += (high - low + 1) * val;
if(low != high) {
lazy[2 * ind + 1] += val;
lazy[2 * ind + 2] += val;
}
return;
}
ll mid = low + (high - low)/2;
// Partial Overlap ke case me left and right dono update karenge
updateRange(l, r, val, low, mid, 2 * ind + 1);
updateRange(l, r, val, mid + 1, high, 2 * ind + 2);
// Since, One Of The Child's Value is Updated
// We have to find minimum again !!!
seg[ind] = seg[2 * ind + 1] + seg[2 * ind + 2];
}
};
struct fenwick {
vector<ll> fn;
ll n;
void init(ll n) {
this->n = n + 1;
fn.resize(this->n, 0);
}
void add(ll x, ll y) {
x++;
while (x < n) {
fn[x] += y;
x += (x & (-x));
}
}
ll sum(ll x) {
x++;
ll ans = 0;
while (x) {
ans += fn[x];
x -= (x & (-x));
}
return ans;
}
ll sum(ll l, ll r) {
return sum(r) - sum(l - 1);
}
};
class DisjointSet {
vector<ll> rank, parent, size;
public:
DisjointSet(ll n) {
rank.resize(n + 1, 0);
parent.resize(n + 1);
size.resize(n + 1, 1);
for(ll i = 1; i <= n; i++) parent[i] = i;
}
void unionByRank(ll x, ll y) {
ll par_x = findPar(x);
ll par_y = findPar(y);
if(par_x == par_y) return;
if(rank[par_x] < rank[par_y]) {
parent[par_x] = par_y;
} else if(rank[par_y] < rank[par_x]) {
parent[par_y] = par_x;
} else {
parent[par_x] = par_y;
rank[par_y]++;
}
}
void unionBySize(ll x, ll y) {
ll par_x = findPar(x);
ll par_y = findPar(y);
if(par_x == par_y) return;
if(size[par_x] < size[par_y]) {
parent[par_x] = par_y;
size[par_y] += size[par_x];
} else {
parent[par_y] = par_x;
size[par_x] += size[par_y];
}
}
ll findPar(ll x) {
if(parent[x] == x) return x;
return parent[x] = findPar(parent[x]);
}
};
ll binpow(ll a,ll b) {
ll ans = 1;
while(b > 0) {
if((b & 1) == 1) ans *= a;
a *= a;
b = b >> 1;
}
return ans;
}
ll binpowmod(ll a,ll b) {
ll ans = 1;
while(b > 0) {
if((b & 1) == 1) {
ans *= a;
ans %= mod;
}
a *= a;
a %= mod;
b = b >> 1;
}
return ans;
}
ll gcd(ll a,ll b) {
if(b == 0) return a;
return gcd(b, a % b);
}
ll lcm(ll a,ll b) {
return (a / gcd(a,b)) * b;
}
const ll MAX = 2e5 + 7;
vector<ll> fact(MAX);
ll add(ll a, ll b) {
return (a + b) % mod;
}
ll sub(ll a, ll b) {
return ((a - b) % mod + mod) % mod;
}
ll mult(ll a, ll b) {
return ((a * b) % mod);
}
ll inv(ll a) {
return binpowmod(a, mod - 2);
}
ll divide(ll a, ll b) {
return mult(a, inv(b));
}
ll nCr(ll n, ll r) {
if(n < r) return 0;
return divide(fact[n], mult(fact[r], fact[n - r]));
}
void preFactorial() {
fact[0] = 1;
for(ll i = 1; i < MAX; i++) fact[i] = mult(i, fact[i - 1]);
}
bool isVowel(char c) {
if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') return true;
if(c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U') return true;
return false;
}
bool isSame(ll n, ll arr[]) {
for(ll i = 0; i < n; i++) {
if(arr[i] != arr[0]) return false;
}
return true;
}
bool isSame(ll n, vector<ll> &arr) {
for(ll i = 0; i < n; i++) {
if(arr[i] != arr[0]) return false;
}
return true;
}
bool isSorted(ll n, ll arr[]) {
for(ll i = 1; i < n; i++) {
if(arr[i] < arr[i - 1]) return false;
}
return true;
}
bool isSorted(ll n, vector<ll> &arr) {
for(ll i = 1; i < n; i++) {
if(arr[i] < arr[i - 1]) return false;
}
return true;
}
void inputArr(ll n, ll arr[]) {
for(ll i = 0; i < n; i++) cin >> arr[i];
}
void inputArr(ll n, vector<ll> &arr) {
ll x;
for(ll i = 0; i < n; i++) {
cin >> x;
arr.push_back(x);
}
}
void printArr(ll n, ll arr[]) {
for(ll i = 0; i < n; i++) cout << arr[i] << " ";
cout << nl;
}
void printArr(ll n, vector<ll> &arr) {
for(ll i = 0; i < n; i++) cout << arr[i] << " ";
cout << nl;
}
ll sumOfArr(ll n, ll arr[]) {
ll ans = 0;
for(ll i = 0; i < n; i++) ans += arr[i];
return ans;
}
ll sumOfArr(ll n, vector<ll> &arr) {
ll ans = 0;
for(ll i = 0; i < n; i++) ans += arr[i];
return ans;
}
bool isPrime(ll n) {
if(n == 1) return false;
for(ll i = 2; i <= sqrt(n); i++) {
if(n % i == 0) return false;
}
return true;
}
ll countSetBits(ll n) {
ll ans = 0;
while(n) {
ans++;
n = n & (n - 1);
}
return ans;
}
vector<ll> primeFactorization(ll n) {
vector<ll> factors;
for(ll i = 2; i * i <= n; i++) {
ll cnt = 0;
while(n % i == 0) {
cnt++;
n /= i;
factors.push_back(i);
}
}
if(n > 1) factors.push_back(n);
return factors;
}
bool isPalindrome(string s) {
ll i = 0;
ll j = s.size() - 1;
while(i <= j) {
if(s[i] != s[j]) return false;
i++;
j--;
}
return true;
}
bool isbiparite ( vector<vector<int>>&graph, vector<int> &color,int c , int node) {
color[ node ] = c;
for( const auto & g : graph[node]) {
if(!color[g]) {
if(!isbiparite(graph,color,!c,g))return false;
}
else if( c==color[g])return false;
}
return true;
}
// double chola ( pair <double , double> pp , double c2) {
// double cd = (pp.F - c2)* ( pp.F - c2 );
// cd = cd/ pp.S;
// cd /=4;
// return cd;
// }
double chola (int curr, pair<double, double> prev , vector< pair< double, double> > & v) {
double r = (v[curr].first - prev.first) * ((v[curr].first - prev.first)) / (4 * prev.second);
return r;
}
void A() {
int n ; cin>>n;
vector< pair< double, double> > a( n );
For ( i , 0 ,n ) cin>>a[i].F>>a[i].S;
double ans = a[ 0].S;
cout <<fixed <<setprecision( 3 );
cout <<ans <<" ";
stack < pair < double , double >> stk;
stk.push( { a[ 0 ].F, a[ 0 ].S});
for ( int i = 1 ; i < n ;i++) {
double R = a[ i].S;
while ( !stk.empty() ) {
double r = chola(i , stk.top(), a);
R = min ( R , r);
if( R >= stk.top().S ) {
stk.pop();
continue;
}
else break;
}
cout<<fixed<<setprecision( 3 );
cout<<R <<" ";
stk.push({ a[i].F , R});
}
}
void B() {
}
void C() {
}
void D() {
}
void E() {
}
int main() {
cin.tie( nullptr);
ios_base::sync_with_stdio( false);
int test = 1;
// cin>>test;
while (test--) {
A();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1880 KB |
10 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1884 KB |
2 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1884 KB |
505 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1880 KB |
2000 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
2648 KB |
20000 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
3928 KB |
50000 numbers |
| 2 |
Correct |
36 ms |
3928 KB |
49912 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
5884 KB |
100000 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
75 ms |
6632 KB |
115362 numbers |
| 2 |
Correct |
67 ms |
6952 KB |
119971 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
102 ms |
8124 KB |
154271 numbers |
| 2 |
Correct |
109 ms |
10128 KB |
200000 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
123 ms |
9296 KB |
200000 numbers |
| 2 |
Correct |
121 ms |
10068 KB |
199945 numbers |
