QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#357417 | #1343. Zombie Land | bdzzj | WA | 2ms | 14312kb | C++14 | 2.9kb | 2024-03-18 21:09:26 | 2024-03-18 21:09:26 |
Judging History
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'