oj.uz

Submission #919696

# Submission time Handle Problem Language Result Execution time Memory
919696 2024-02-01T13:05:20 Z penguin133 Balloons (CEOI11_bal) C++17
100 / 100
 184 ms 11740 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

struct line{
	long double m, c;
	line(){
		m = 0, c = 2e18;
	}
	line(long double _m, long double _c){
		m = _m, c = _c;
	}
	long double operator () (int x) {return m * x + c;}
};

struct node{
	int s,e;
	line ln;
	node *l = nullptr, *r = nullptr;
	node(int _s, int _e){
		s = _s, e = _e;
		
	}
	void mc(){
		if(l != nullptr)return;
		if(s + 1 < e){
			l = new node(s, s+e>>1);
			r = new node(s+e>>1 ,e);
		}
	}
	void upd(line nl){
		if(s + 1 == e){
			if(ln(s) > nl(s))ln = nl;
			return;
		}
		bool lf = (ln(s) < nl(s)), f = 0, rt = (ln(e) < nl(e));
		if(ln(s+e>>1) > nl(s+e>>1))swap(ln, nl), f = 1;
		if((nl.m == 0 && nl.c == 2e18) || lf == rt)return;
		mc();
		if(f != lf)r->upd(nl);
		else l->upd(nl);
	}
	long double query(int x){
		if(l == nullptr || (s + 1 == e))return ln(x);
		else if(x < s+e>>1)return min(ln(x), l->query(x));
		else return min(ln(x), r->query(x));
	}
}*root;
int n, X[200005], R[200005];

void solve(){
	cin >> n;
	root = new node(-1e9, 1e9);
	cout << fixed << setprecision(3);
	for(int i = 1; i <= n; i++){
		cin >> X[i] >> R[i];
		if(i == 1){
			cout << R[i] << '\n';
			root->upd(line((long double)(1) / (2 * sqrtl(R[i])), (long double)(-X[i]) / (2 * sqrtl(R[i]))));
		}
		else {
			long double tmp = root->query(X[i]);
			tmp *= tmp;
			tmp = min(tmp, (long double)(R[i]));
			cout << tmp << '\n';
			root->upd(line((long double)(1) / (2 * sqrtl(tmp)), (long double)(-X[i]) / (2 * sqrtl(tmp))));
		} 
	}
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message

bal.cpp: In member function 'void node::mc()':
bal.cpp:36:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |    l = new node(s, s+e>>1);
      |                    ~^~
bal.cpp:37:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |    r = new node(s+e>>1 ,e);
      |                 ~^~
bal.cpp: In member function 'void node::upd(line)':
bal.cpp:46:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |   if(ln(s+e>>1) > nl(s+e>>1))swap(ln, nl), f = 1;
      |         ~^~
bal.cpp:46:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |   if(ln(s+e>>1) > nl(s+e>>1))swap(ln, nl), f = 1;
      |                      ~^~
bal.cpp: In member function 'long double node::query(long long int)':
bal.cpp:54:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |   else if(x < s+e>>1)return min(ln(x), l->query(x));
      |               ~^~
bal.cpp: At global scope:
bal.cpp:80:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   80 | main(){
      | ^~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3672 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 4924 KB 50000 numbers
2 Correct 36 ms 3664 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 5968 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 6228 KB 115362 numbers
2 Correct 81 ms 5200 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 7260 KB 154271 numbers
2 Correct 136 ms 6992 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 11740 KB 200000 numbers
2 Correct 144 ms 7392 KB 199945 numbers