QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#357417#1343. Zombie LandbdzzjWA 2ms14312kbC++142.9kb2024-03-18 21:09:262024-03-18 21:09:26

Judging History

This is the latest submission verdict.

  • [2024-03-18 21:09:26]
  • Judged
  • Verdict: WA
  • Time: 2ms
  • Memory: 14312kb
  • [2024-03-18 21:09:26]
  • Submitted

answer

#include<bits/stdc++.h>
#define N 200005
#define ll long long
#define LL __int128
using namespace std;
const ll JD=1<<30,INFll=3e18;
const LL _1=1,INF=1e36;
int n,v0;
ll x0,ans[N];
struct node{
	ll x;
	int v,id;
}a[N];
inline bool cmp(node a,node b){return a.x<b.x;}
struct line{
	int k;
	LL b;
	inline LL calc(ll x){return _1*k*x+b;}
};
namespace tree1{
	line tree[N];
	int root,cnt,L[N],R[N];
	LL mn[N];
	inline int news(){
		cnt++;
		tree[cnt]=(line){0,INF};
		mn[cnt]=INF;
		L[cnt]=R[cnt]=0;
		return cnt;
	}
	void inserts(int &rt,ll l,ll r,line v){
		if(!rt){
			rt=news();
			tree[rt]=v;
			mn[rt]=v.calc((l+r)>>1);
			return;
		}
		ll mid=(l+r)>>1;
		mn[rt]=min(mn[rt],v.calc(mid));
		if(v.calc(mid)<tree[rt].calc(mid)) swap(tree[rt],v);
		if(l==r) return;
		if(v.calc(l)<tree[rt].calc(l)) inserts(L[rt],l,mid,v);
		if(v.calc(r)<tree[rt].calc(r)) inserts(R[rt],mid+1,r,v);
		return;
	}
	ll query(int rt,ll l,ll r,line li){
		if(!rt) return INFll;
		ll ans=INFll;
		if(li.k>tree[rt].k) ans=(tree[rt].b-li.b+li.k-tree[rt].k-1)/(li.k-tree[rt].k);
		if(l!=r){
			ll mid=(l+r)>>1;
			if(mn[rt]<=li.calc(mid)) ans=min(ans,query(L[rt],l,mid,li));
			else ans=min(ans,query(R[rt],mid+1,r,li));
		}
		return ans;
	}
}
namespace tree2{
	line tree[N];
	int root,cnt,L[N],R[N];
	LL mx[N];
	inline int news(){
		cnt++;
		tree[cnt]=(line){0,-INF};
		mx[cnt]=-INF;
		L[cnt]=R[cnt]=0;
		return cnt;
	}
	void inserts(int &rt,ll l,ll r,line v){
		if(!rt){
			rt=news();
			tree[rt]=v;
			mx[rt]=v.calc((l+r)>>1);
			return;
		}
		ll mid=(l+r)>>1;
		mx[rt]=max(mx[rt],v.calc(mid));
		if(v.calc(mid)>tree[rt].calc(mid)) swap(tree[rt],v);
		if(l==r) return;
		if(v.calc(l)>tree[rt].calc(l)) inserts(L[rt],l,mid,v);
		if(v.calc(r)>tree[rt].calc(r)) inserts(R[rt],mid+1,r,v);
		return;
	}
	ll query(int rt,ll l,ll r,line li){
		if(!rt) return INFll;
		ll ans=INFll;
		if(li.k<tree[rt].k) ans=(li.b-tree[rt].b+tree[rt].k-li.k-1)/(tree[rt].k-li.k);
		if(l!=r){
			ll mid=(l+r)>>1;
			if(mx[rt]>=li.calc(mid)) ans=min(ans,query(L[rt],l,mid,li));
			else ans=min(ans,query(R[rt],mid+1,r,li));
		}
		return ans;
	}
}
int main(){
	scanf("%d",&n);
	scanf("%lld%d",&x0,&v0);
	x0*=JD;
	for(int i=1;i<=n;i++) scanf("%lld%d",&a[i].x,&a[i].v),a[i].id=i;
	for(int i=1;i<=n;i++) a[i].x*=JD;
	sort(a+1,a+n+1,cmp);
	int p=0;
	while(p+1<=n&&a[p+1].x<x0) p++;
	for(int i=p+1;i<=n;i++) tree1::inserts(tree1::root,0,INFll,(line){a[i].v,a[i].x});
	tree1::inserts(tree1::root,0,INFll,(line){v0,x0});
	for(int i=1;i<=p;i++) ans[a[i].id]=tree1::query(tree1::root,0,INFll,(line){a[i].v,a[i].x});
	for(int i=1;i<=p;i++) tree2::inserts(tree2::root,0,INFll,(line){a[i].v,a[i].x});
	tree2::inserts(tree2::root,0,INFll,(line){v0,x0});
	for(int i=p+1;i<=n;i++) ans[a[i].id]=tree2::query(tree2::root,0,INFll,(line){a[i].v,a[i].x});
	for(int i=1;i<=n;i++){
		if(ans[i]==INFll) puts("-1");
		else printf("%.9f\n",ans[i]*1./JD);
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 14312kb

input:

6
3 1
-5 0
5 0
-4 -3
0 -2
6 -3
2 -1

output:

3.666666667
2.000000000
-1
6.000000000
0.750000000
2.000000000

result:

ok 6 numbers

Test #2:

score: 0
Accepted
time: 2ms
memory: 14124kb

input:

5
31415 -926
5358 979
323846 26
-433832 7950
288 -4
-1971 -69

output:

13.678215223
95.618122161
52.416291122
33.760303688
38.956826138

result:

ok 5 numbers

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 12008kb

input:

972
98740224 301565350
897445571 19067267
-528259301 772813962
88724382 432443246
668138287 561147750
-111697007 795680328
716395194 388109596
-289144978 72929322
-935429651 690324478
632898250 -359347321
-388094843 -753263424
416481084 91553128
460683861 290773570
445572029 -788653120
-239712630 23...

output:

0.855538052
0.373207831
0.011835082
1.450834986
0.127333456
1.093110812
0.395160592
0.641783245
0.407945346
2.445301046
0.370335431
0.547955469
0.200072537
0.298295899
0.237186775
0.701505527
2.384034582
0.554621879
0.282706399
0.593895907
1.903701435
0.291040036
2.062266751
4.178873286
0.274588316
...

result:

wrong answer 1st numbers differ - expected: '0.8555381', found: '0.8555381', error = '0.0000000'