Submission #653382

#	Time	Username	Problem	Language	Result	Execution time	Memory
653382		Antekb	Balloons (CEOI11_bal)	C++14	80 / 100	1619 ms	65536 KiB

bal

#include<bits/stdc++.h>
 
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("trapv")
 
#define st first
#define nd second
#define pb push_back
#define pp pop_back
#define eb emplace_back
#define mp(a, b) make_pair(a, b)
#define all(x) (x).begin(), (x).end()
#define rev(x) reverse(all(x))
#define sor(x) sort(all(x))
#define sz(x) (int)(x).size()
#define rsz(x) resize(x)
 
using namespace std;
 
///~~~~~~~~~~~~~~~~~~~~~~~~~~
 
template <typename H, typename T> 
ostream& operator<<(ostream& os, pair<H, T> m){
	return os <<"("<< m.st<<", "<<m.nd<<")";
}
template <typename H> 
ostream& operator<<(ostream& os, vector<H> V){
	os<<"{";
	for(int i=0; i<V.size(); i++){
		if(i)os<<" ";
		os<<V[i];
	}
	os<<"}";
	return os;
}
 
void debug(){cerr<<"\n";}
template <typename H, typename... T>
void debug(H h, T... t) {cerr<<h; if (sizeof...(t)) cerr << ", "; debug(t...);}
#define deb(x...) cerr<<#x<<" = ";debug(x);
 
///~~~~~~~~~~~~~~~~~~~~~~~~~
 
typedef long long ll;
typedef double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii > vii;
typedef vector<ll> vl;
typedef vector<pll> vll;
typedef string str;
 
#define BOOST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
 
const int N=2e5+5, mod=1e9+7, INF=(1<<30);
const ld EPS=1e-5;
struct line{
	ld a, b;
	line(ld a, ld b): a(a), b(b){}
	ld isect(line L){
		return (b-L.b)/(L.a-a);
	}
	ld val(ld x){return a*x+b;}
};
vi L, R;
vector<line> lines;
vector<int> li;
vector<int> l, r;
vector<vector<pair<int, pair<int, int> > > > todo;
void insert(int v, int li2, int l1, int r1){
		//deb(l, r, li.a, li.b);
		//deb(l1, r1, li2.a, li2.b);
		if(lines[li2].val(l[v])>lines[li[v]].val(l[v])-EPS && lines[li2].val(r[v])>lines[li[v]].val(r[v])-EPS)return;
		//deb("a");
		if(l1==l[v] && r1==r[v] && lines[li2].val(l[v])<lines[li[v]].val(l[v]) && lines[li2].val(r[v])<lines[li[v]].val(r[v])){
			li[v]=li2;
			return;
		}
		if(l[v]==r[v])return;
		int m=l[v]+(r[v]-l[v])/2;
		if(!L[v]){
			L[v]=L.size();
			L.pb(0), R.pb(0);
			l.pb(l[v]);
			r.pb(m);
			todo.pb({});
			li.pb(0);
			R[v]=L.size();
			L.pb(0), R.pb(0);
			r.pb(r[v]);
			l.pb(m+1);
			todo.pb({});
			li.pb(0);
		}
		if(l1<=m)todo[L[v]].pb({li2, {l1, min(r1, m)}});
		if(r1>m)todo[R[v]].pb({li2, {max(l1, m+1), r1}});
		return;
}
ld val(int v, int x){
		ld ans=lines[li[v]].val(x);
		int k=0;//=max(int(todo[v].size())/2, 500);
		if(todo.size()>3000 || r[v]-l[v]>10000)k=0;
		else k=todo.size()/2;
		while(todo[v].size()>k){
			//assert(todo[v].size());
			insert(v, todo[v].back().st, todo[v].back().nd.st, todo[v].back().nd.nd);
			todo[v].pp();
		}
		//if(todo[v].size()<5000){
		for(auto &i:todo[v]){
			if(x>=i.nd.st && x<=i.nd.nd)ans=min(ans, lines[i.st].val(x));
		}
		//}
		ans=min(ans, lines[li[v]].val(x));
		int m=l[v]+(r[v]-l[v])/2;
		if(x<=m && L[v])ans=min(ans, val(L[v], x));
		else{
			if(R[v])ans=min(ans, val(R[v], x));
		}
		return ans;
}

int main(){
	//BOOST;
	int n;
	cin>>n;
	int root=0;
	L.pb(0), R.pb(0);
	l.pb(0);
	r.pb(INF);
	todo.pb({});
	li.pb(0);
	lines.pb(line(0, INF));
	for(int i=0; i<n; i++){
		int x, rr;
		cin>>x>>rr;
		ld r2=val(root, x);
		r2=min(r2*r2, ld(rr));
		cout<<fixed<<setprecision(3)<<r2<<"\n";
		if(r2>EPS){
			lines.pb(line(-1/ld(2*sqrt(r2)), x/ld(2*sqrt(r2))));
			insert(root, lines.size()-1, 0, x);
			lines.pb(line(1/ld(2*sqrt(r2)), -x/ld(2*sqrt(r2))));
			insert(root, lines.size()-1, x+1, INF);
		}
	}
}

Compilation message (stderr)

bal.cpp: In function 'ld val(int, int)':
bal.cpp:107:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  107 |   while(todo[v].size()>k){
      |         ~~~~~~~~~~~~~~^~

• 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: 0 / 10
• Subtask 10: 0 / 10