Submission #1281716

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281716		WH8	Balloons (CEOI11_bal)	C++20	20 / 100	278 ms	11492 KiB

bal

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define ld long double
	
signed main(){
	int n;cin>>n;
	vector<int> x(n);
	vector<ld> y(n), lim(n);
	for(int i=0;i<n;i++)cin>>x[i]>>lim[i];
	set<pair<ld, int>> st; // {y[i], i}
	priority_queue<pair<ld, int>,vector<pair<ld,int>>,greater<pair<ld,int>>> pq; // {life, i}
	for(int i=0;i<n;i++){
		//~ cout<<i<<endl;
		while(!pq.empty() and pq.top().f <= x[i]){
			auto [co, di]=pq.top();
			//~ printf("died %lld, co was %Lf\n", di, co);
			pq.pop();
			auto todel=st.lower_bound(mp(y[di], -1));
			if(todel != st.end() and (*todel).f == y[di]) st.erase(todel);
			// calculate the next cutoff. 
			auto it1=st.lower_bound(mp(y[di], -1));
			if(it1 != st.begin()){
				auto it2=prev(it1);
				int a=(*it1).s, b=(*it2).s;
				//~ printf("life of indices %lld, %lld, x1 %lld, x2 %lld, y1 %Lf, y2 %Lf\n", a,b,x[a],x[b],y[a],y[b]); 
				//~ fflush(stdout);
				ld r=sqrt(y[a]/y[b]);
				ld life=(r*x[b]-x[a])/(r-1);
				// delete b when 
				pq.push({life, b});
			}
		}
		// calculate max. 
		if(st.empty()) y[i]=lim[i];
		else {
			auto [py, pi]=*st.begin();
			y[i]=(x[i]-x[pi])/(2*sqrt(py));
			y[i]=y[i]*y[i];
			y[i]=min(y[i], lim[i]);
		}
		while(!st.empty() and (*st.begin()).f < y[i]){
			st.erase(st.begin());
		}
		// calculate life of current.
		if(!st.empty()){
			int a=(*st.begin()).s, b=i;
			ld r=sqrt(y[a]/y[b]);
			ld life=(r*x[b]-x[a])/(r-1);
			pq.push({life, b});
		}
		st.insert({y[i], i});
		//~ cout<<i<<endl;
	}
	cout<<fixed<<setprecision(3);
	for(int i=0;i<n;i++){
		cout<<y[i]<<" ";
	}
}

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