| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1078553 |
2024-08-27T20:43:03 Z |
BoggyMan |
Balloons (CEOI11_bal) |
C++14 |
|
137 ms |
9356 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++) {
// cout <<"koli "<<chola( stk.top() , a[i].F) <<endl;
bool f = false;
pair <double ,double> pipo;
while ( !stk.empty() &&chola( i, stk.top() , a) > a[i].S) {
f = true;
pipo = stk.top();
stk.pop();
}
double tmp = 0;
if (!stk.empty())
tmp = chola( i, stk.top() , a);
else tmp = a[i].S;
cout <<fixed <<setprecision( 3 );
cout <<tmp <<" ";
if ( f ) {
if(pipo.F + pipo.S >= tmp + a[i].F)stk.push(pipo);
else stk.push ( { a[ i].F , tmp });
}
else
stk.push ( { a[ i].F , tmp });
}
}
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 |
1884 KB |
10 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1884 KB |
2 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1880 KB |
12th numbers differ - expected: '5.1130000000', found: '5.3100000000', error = '0.1970000000' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1884 KB |
114th numbers differ - expected: '39.0180000000', found: '56.0000000000', error = '16.9820000000' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
2652 KB |
196th numbers differ - expected: '100.7250000000', found: '109.4560000000', error = '8.7310000000' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
3920 KB |
13946th numbers differ - expected: '0.0440000000', found: '2215.6580000000', error = '2215.6140000000' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
68 ms |
5716 KB |
7238th numbers differ - expected: '0.0400000000', found: '927.9360000000', error = '927.8960000000' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
80 ms |
6480 KB |
4652nd numbers differ - expected: '0.4350000000', found: '0.5930000000', error = '0.1580000000' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
106 ms |
8016 KB |
1730th numbers differ - expected: '5.6890000000', found: '6.8060000000', error = '1.1170000000' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
137 ms |
9356 KB |
2723rd numbers differ - expected: '859.0470000000', found: '862.0000000000', error = '2.9530000000' |
| 2 |
Halted |
0 ms |
0 KB |
- |
