QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#243938 | #7520. Monster Generator | qwqwf | WA | 1ms | 3612kb | C++14 | 2.5kb | 2023-11-08 19:28:26 | 2023-11-08 19:28:26 |
Judging History
answer
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#pragma GCC optimize("Ofast","unroll-loops","inline")
#include<bits/stdc++.h>
#define ll long long
//#define int ll
#define ull unsigned ll
#define i128 __int128_t
using namespace std;
const int N=225,M=1e6+20,mod=998244353;
int n,m,day,e[N*N],id[N],s[N],t[N];
ull ans;
struct Node{ll a,b,da,db;}p[N];
struct P{
i128 a,b;int sgn;
P(){}
P(i128 _a,i128 _b){a=_a,b=_b;if(a<b) sgn=1;else if(a==b) sgn=0;else sgn=-1;}
}vl[N],vr[N];
inline int cmp(const P &x,const P &y){
if(x.sgn!=y.sgn) return x.sgn>y.sgn?-1:1;
if(x.a==x.b) return 0;
if(x.a<x.b){
if(x.a==y.a) return 0;
return x.a<y.a?-1:1;
}
else{
if(x.b==y.b) return 0;
return x.b>y.b?-1:1;
}
}
inline bool cmpid(int x,int y){
int w=cmp(vl[x],vl[y]);
if(w) return w<0;
return cmp(vr[x],vr[y])<0;
}
struct Line{ll k,b;}line[N],h[N];
inline bool cmpl(const Line &x,const Line &y){
if(x.k!=y.k) return x.k<y.k;
return x.b>y.b;
}
inline void calc(const Line &x,ll l,ll r){
if(l>r) return ;
ans+=(l+r)*(r-l+1)/2*x.k+x.b*(r-l+1);
}
void solve(int l,int r){
if(l>r) return ;
for(int i=1;i<=n;i++) id[i]=i,vl[i]=P(p[i].a+p[i].da*l,p[i].b+p[i].db*l),vr[i]=P(p[i].a+p[i].da*r,p[i].b+p[i].db*r);
sort(id+1,id+n+1,cmpid);
ll sk=0,sb=0;
line[0].k=line[0].b=0;
for(int i=1;i<=n;i++){
int u=id[i];
sk+=p[u].da;sb+=p[u].a;
line[i].k=sk;line[i].b=sb;
sk-=p[u].db;sb-=p[u].b;
}
sort(line+1,line+n+1,cmpl);
int tp=0;
for(int i=0;i<=n;i++) if(!i||line[i].k>line[i-1].k){
while(tp>1&&(h[tp-1].b-h[tp].b)*(line[i].k-h[tp].k)>=(h[tp].b-line[i].b)*(h[tp].k-h[tp-1].k)) tp--;
h[++tp]=line[i];
}
for(int i=1;i<=tp;i++) s[i]=l,t[i]=r;
for(int i=1;i<tp;i++){
ll u=h[i].b-h[i+1].b,v=h[i+1].k-h[i].k;
if(u<0){t[i]=-1;continue;}
u/=v;if(u<t[i]) t[i]=u;
++u;
if(u>r) s[i+1]=r+1;
else if(u>s[i+1]) s[i+1]=u;
}
for(int i=1;i<=tp;i++) calc(h[i],s[i],t[i]);
}
inline void split(ll b1,ll k1,ll b2,ll k2){
if(k1==k2) return ;
ll u=b2-b1,v=k1-k2;
if(v<0) u*=-1,v*=-1;
if(u<=0) return ;
u/=v;
if(u>=day) return ;
e[++m]=u;
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>day;
e[++m]=-1;e[++m]=day;
for(int i=1;i<=n;i++) cin>>p[i].a>>p[i].da>>p[i].b>>p[i].db,split(p[i].a,p[i].da,p[i].b,p[i].db);
for(int i=1;i<=n;i++) for(int j=1;j<i;j++){
split(p[i].a,p[i].da,p[j].b,p[j].db);
}
sort(e+1,e+m+1);
for(int i=1;i<m;i++) solve(e[i]+1,e[i+1]);
cout<<ans<<'\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3572kb
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: 1ms
memory: 3572kb
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: 3612kb
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:
0
result:
wrong answer 1st lines differ - expected: '17883317185357051350', found: '0'