oj.uz

Submission #244304

# Submission time Handle Problem Language Result Execution time Memory
244304 2020-07-03T15:01:52 Z TadijaSebez Balloons (CEOI11_bal) C++11
100 / 100
 456 ms 12164 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB 10 numbers

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB 2 numbers

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB 505 numbers

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 512 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 1400 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 4108 KB 50000 numbers
2 Correct 107 ms 3448 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 6520 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 7416 KB 115362 numbers
2 Correct 237 ms 7440 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 9336 KB 154271 numbers
2 Correct 408 ms 12164 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 456 ms 11768 KB 200000 numbers
2 Correct 373 ms 12024 KB 199945 numbers