QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#548080 | #7520. Monster Generator | Yoralen | WA | 2ms | 14012kb | C++14 | 2.5kb | 2024-09-05 15:17:20 | 2024-09-05 15:17:20 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
typedef unsigned long long ull;
const int N=100005;
struct Line{
long double k,b;
bool operator ==(Line A)const{
return k==A.k&&b==A.b;
}
}st[N],stl[N];
int n,tp;
long double It,m,stt[N],inf=1e18;
ull ans;
long double Int(Line l1,Line l2){return (l2.b-l1.b)/(l1.k-l2.k);}
struct node{long double a,ka,b,kb;}st1[N],st2[N],a[N];
void Ins(Line l){
while(tp>=2&&Int(l,st[tp-1])<=Int(st[tp-1],st[tp]))tp--;
if(tp==1&&Int(st[tp],l)<=It)tp--;st[++tp]=l;
}
bool cmp(Line l1,Line l2){return l1.k<l2.k||(l1.k==l2.k&&l1.b>l2.b);}
bool cmp1(node A,node B){return A.a+It*A.ka<B.a+It*B.ka;}
bool cmp2(node A,node B){return A.b+It*A.kb>B.b+It*B.kb;}
signed main(){
int i,j,tpt=0;
scanf("%lld%Lf",&n,&m);//cout<<inf<<'\n';
for(i=1;i<=n;i++){
scanf("%Lf%Lf%Lf%Lf",&a[i].a,&a[i].ka,&a[i].b,&a[i].kb);
if(a[i].ka!=a[i].kb){
long double v=(a[i].b-a[i].a)/(a[i].ka-a[i].kb);
if(v>0&&v<m)stt[++tpt]=v;
}
}
for(i=1;i<n;i++){
for(j=i+1;j<=n;j++){
if(a[i].ka!=a[j].ka){
long double v=(a[j].a-a[i].a)/(a[i].ka-a[j].ka);
if(v>0&&v<m)stt[++tpt]=v;
}
if(a[i].kb!=a[j].kb){
long double v=(a[j].b-a[i].b)/(a[i].kb-a[j].kb);
if(v>0&&v<m)stt[++tpt]=v;
}
}
}
sort(stt+1,stt+1+tpt);
long double l=0,r;int L=0,R;
for(i=0;i<=tpt;i++){
if(i<tpt)r=stt[i+1];
else r=m;R=(int)(r);
if(L<=R){
// printf("!%lf %lf %lld %lld\n",l,r,L,R);
int tp1=0,tp2=0;
for(j=1;j<=n;j++){
if(a[j].b+a[j].kb*L>=a[j].a+a[j].ka*L)st1[++tp1]=a[j];
else st2[++tp2]=a[j];
}
It=(l+r)/2.0;
sort(st1+1,st1+1+tp1,cmp1);
sort(st2+1,st2+1+tp2,cmp2);
long double B=0,K=0;int tpl=0;
for(j=1;j<=tp1;j++){
B+=st1[j].a,K+=st1[j].ka;
stl[++tpl]=(Line){K,B};
B-=st1[j].b,K-=st1[j].kb;
}
for(j=1;j<=tp2;j++){
B+=st2[j].a,K+=st2[j].ka;
stl[++tpl]=(Line){K,B};
B-=st2[j].b,K-=st2[j].kb;
}
sort(stl+1,stl+1+tpl,cmp);tp=0;
for(j=1;j<=tpl;j++){
if(j==1||stl[j].k!=stl[j-1].k)Ins(stl[j]);
}
long double lim=L,rim;
int Cl=L,Cr;
for(j=1;j<=tp;j++){
if(j<tp)rim=Int(st[j],st[j+1]);
else rim=inf;
Cr=min(R,(int)rim);
// printf("@%lf %lf %lld %lld\n",st[j].k,st[j].b,Cl,Cr);
if(Cl<=Cr){
ull v1=(ull)(st[j].b),v2=(ull)(Cr-Cl+1);
ull v3=(ull)(st[j].k),v4=(ull)(Cl+Cr);
ans=ans+v1*v2+v3*v4*v2/2;
}
lim=rim;Cl=Cr+1;
if(Cr==R)break;
}
}
l=r;L=R+1;
}
cout<<ans;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 12028kb
input:
3 5 3 1 5 2 4 2 1 3 1 9 100 1
output:
113
result:
ok single line: '113'
Test #2:
score: 0
Accepted
time: 0ms
memory: 12028kb
input:
3 100000000 3 1 5 2 4 2 1 3 1 9 100 1
output:
35000000549999998
result:
ok single line: '35000000549999998'
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 14012kb
input:
10 1000000000000000000 776874380544333 197 471391764744275 33 159838820333814 107 677112662750393 41 962335658276824 48 255593531071176 11 127404116579775 209 268525254990127 34 647620110614714 76 897947476313307 13 146196843402516 221 772928712898807 39 637929916804442 2 716937021892338 15 64200226...
output:
8659945148502275542
result:
wrong answer 1st lines differ - expected: '17883317185357051350', found: '8659945148502275542'