oj.uz

Submission #220602

# Submission time Handle Problem Language Result Execution time Memory
220602 2020-04-08T07:06:33 Z arnold518 Balloons (CEOI11_bal) C++14
100 / 100
 191 ms 12148 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;

int N;
ll X[MAXN+10];
long double R[MAXN+10];

int main()
{
	int i, j;

	scanf("%d", &N);
	for(i=1; i<=N; i++) scanf("%lld%Lf", &X[i], &R[i]);

	vector<int> S;
	for(i=1; i<=N; i++)
	{
		while(!S.empty())
		{
			R[i]=min(R[i], (long double)(X[i]-X[S.back()])*(X[i]-X[S.back()])/(4*R[S.back()]));
			if(R[i]<=R[S.back()]) break;
			else S.pop_back();
		}
		S.push_back(i);
	}

	for(i=1; i<=N; i++) printf("%.10Lf\n", R[i]);
}

Compilation message

bal.cpp: In function 'int main()':
bal.cpp:16:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
bal.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
bal.cpp:19:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=N; i++) scanf("%lld%Lf", &X[i], &R[i]);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 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 7 ms 512 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1408 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 3192 KB 50000 numbers
2 Correct 43 ms 3320 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 5856 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 6744 KB 115362 numbers
2 Correct 123 ms 7412 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 8696 KB 154271 numbers
2 Correct 166 ms 12148 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 10744 KB 200000 numbers
2 Correct 155 ms 12016 KB 199945 numbers