Submission #1143664

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143664		liangjeremy	Balloons (CEOI11_bal)	C++20	100 / 100	118 ms	15580 KiB

bal

#include<bits/stdc++.h>
#include<random>
using namespace std;
using db=double;
using ll=long long;
using sll=__int128;//super long long
using lb=long double;//lb is slow
//numbers for hashing: b(19260817),mod(998244353)
// freopen("fencedin.in", "r", stdin);
// freopen("fencedin.out", "w", stdout);

struct ballon{
	ll coor;
	lb radius;
};

int main(){
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n; cin>>n; vector<ballon>v(n);
	for(ll i=0; i<n; i++){
		cin>>v[i].coor>>v[i].radius;
	}
	stack<ballon>st; vector<lb>ans(n);
	for(ll i=0; i<n; i++){
		lb rd=v[i].radius; bool flag=true;
		while(!st.empty() && flag){
			rd=min(rd,(st.top().coor-v[i].coor)*(st.top().coor-v[i].coor)/(4*st.top().radius));
			if(rd>st.top().radius)st.pop();
			else flag=false;
		}
		ans[i]=rd; st.push({v[i].coor,rd});
	}
	for(auto x:ans){
		cout<<fixed<<setprecision(10)<<x<<'\n';
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10