oj.uz

Submission #538310

# Submission time Handle Problem Language Result Execution time Memory
538310 2022-03-16T15:12:12 Z pawned Balloons (CEOI11_bal) C++17
100 / 100
 300 ms 8516 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<double, double> dd;
typedef vector<int> vi;

int main() {
	int N;
	cin>>N;
	double x[N];
	double r[N];
	for (int i = 0; i < N; i++) {
		cin>>x[i]>>r[i];
	}
/*
	cout<<"start: ";
	for (int i = 0; i < N; i++) {
		printf("%.3f ", r[i]);
	}
*/
	stack<dd> s;
	s.push({x[0], r[0]});
	for (int i = 1; i < N; i++) {
//		cout<<"at "<<i<<endl;
		if (s.size() > 0)
			r[i] = min(r[i], (x[i] - s.top().fi) * (x[i] - s.top().fi) / 4 / s.top().se);
		while (s.size() > 0 && s.top().se <= r[i]) {
			s.pop();
			if (s.size() > 0)
				r[i] = min(r[i], (x[i] - s.top().fi) * (x[i] - s.top().fi) / 4 / s.top().se);
		}
		s.push({x[i], r[i]});
//		cout<<"done "<<i<<endl;
	}
	for (int i = 0; i < N; i++) {
		printf("%.3f\n", r[i]);
	}
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 948 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 2336 KB 50000 numbers
2 Correct 83 ms 2324 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 4380 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 4952 KB 115362 numbers
2 Correct 174 ms 5340 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 6388 KB 154271 numbers
2 Correct 300 ms 8516 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 7632 KB 200000 numbers
2 Correct 290 ms 8508 KB 199945 numbers