Submission #919696

#	Time	Username	Problem	Language	Result	Execution time	Memory
919696		penguin133	Balloons (CEOI11_bal)	C++17	100 / 100	184 ms	11740 KiB

bal

#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 (stderr)

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 / 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