Submission #244304

#	Time	Username	Problem	Language	Result	Execution time	Memory
244304		TadijaSebez	Balloons (CEOI11_bal)	C++11	100 / 100	456 ms	12164 KiB

bal

#include <bits/stdc++.h>
using namespace std;
#define ldb long double
#define pii pair<int,int>
const int N=200050;
const int inf=1e9+7;
int x[N],r[N];
ldb ans[N];
int nxt[N],pre[N],n;
set<pii> events;
int calc(int a,int b){
	ldb A=ans[b]-ans[a];
	ldb B=-2*(ans[b]*x[a]-ans[a]*x[b]);
	ldb C=(ldb)x[a]*x[a]*ans[b]-(ldb)x[b]*x[b]*ans[a];
	ldb D=B*B-4*A*C;
	if(D>=0){
		ldb rD=sqrt(D);
		ldb x1=(-B+rD)/(2*A);
		ldb x2=(-B-rD)/(2*A);
		ldb X=max(x1,x2);
		if(X>max(x[a],x[b])){
			if(X>inf)return inf;
			else return ceil(X);
		}else return inf;
	}else return inf;
}
void Cons(int a,int b){
	if(a!=n+1&&b!=0)
		events.insert({calc(a,b),a});
}
void Del(int a,int b){
	if(a!=n+1&&b!=0)
		events.erase({calc(a,b),a});
}
int main(){
	scanf("%i",&n);
	for(int i=1;i<=n;i++)scanf("%i %i",&x[i],&r[i]);
	for(int i=1;i<=n;i++){
		while(events.size()&&events.begin()->first+1<=x[i]){
			int j=events.begin()->second;
			Del(j,nxt[j]);
			Del(pre[j],j);
			int a=pre[j],b=nxt[j];
			if(a)nxt[a]=b;
			if(b)pre[b]=a;
			Cons(a,b);
		}
		ans[i]=r[i];
		for(int j=nxt[n+1],cnt=0;j&&cnt<100;j=nxt[j],cnt++){
			ldb dx=x[i]-x[j];
			ans[i]=min(ans[i],dx*dx/(4*ans[j]));
		}
		/*for(int j=1;j<i;j++){
			ldb dx=x[i]-x[j];
			ans[i]=min(ans[i],dx*dx/(4*ans[j]));
		}*/
		nxt[i]=nxt[n+1];
		pre[i]=n+1;
		if(nxt[n+1])pre[nxt[n+1]]=i;
		nxt[n+1]=i;
		Cons(i,nxt[i]);
		printf("%.3Lf\n",ans[i]);
	}
	return 0;
}

Compilation message (stderr)

bal.cpp: In function 'int main()':
bal.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
bal.cpp:37:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++)scanf("%i %i",&x[i],&r[i]);
                       ~~~~~^~~~~~~~~~~~~~~~~~~~~

• 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