QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#243959 | #7520. Monster Generator | qwqwf | WA | 1ms | 3488kb | C++14 | 4.2kb | 2023-11-08 19:42:05 | 2023-11-08 19:42:05 |
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 long long
#define i128 __int128
using namespace std;
const int N=225,M=1e6+20,mod=998244353;
namespace FastIO {
struct IO {
char ibuf[(1 << 20) + 1], *iS, *iT, obuf[(1 << 20) + 1], *oS;
IO() : iS(ibuf), iT(ibuf), oS(obuf) {}
~IO() { fwrite(obuf, 1, oS - obuf, stdout); }
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
inline bool eof (const char &ch) { return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t' || ch == EOF; }
template<typename T = int>
inline T read() {
char ch = gh();
T x = 0;
bool t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
return t ? ~(x - 1) : x;
}
inline void read (char *s) {
char ch = gh();
int l = 0;
while (eof(ch)) ch = gh();
while (!eof(ch)) s[l++] = ch, ch = gh();
}
inline void pc (char ch) {
if (oS == obuf + (1 << 20) + 1) fwrite(obuf, 1, oS - obuf, stdout), oS = obuf;
*oS++ = ch;
}
template<typename _Tp>
inline void write (_Tp x) {
static char stk[64], *tp = stk;
if (x < 0) x = ~(x - 1), pc('-');
do *tp++ = x % 10, x /= 10;
while (x);
while (tp != stk) pc((*--tp) | 48);
}
inline void write (char *s) {
int n = strlen(s);
for (int i = 0; i < n; i++) pc(s[i]);
}
} io;
inline int read () { return io.read(); }
inline long long rdl () { return io.read<long long>(); }
template<typename Tp>
inline void read (Tp &x) { io.read(x); }
template<typename _Tp>
inline void write (_Tp x) { io.write(x); }
}
using namespace FastIO;
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+=(ull)((i128)(l+r)*(r-l+1)/2)*x.k+(ull)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+(i128)p[i].da*l,p[i].b+(i128)p[i].db*l),vr[i]=P(p[i].a+(i128)p[i].da*r,p[i].b+(i128)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(){
n=read();day=read();
e[++m]=-1;e[++m]=day;
for(int i=1;i<=n;i++) p[i].a=read(),p[i].da=read(),p[i].b=read(),p[i].db=read(),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]);
write(ans);io.pc('\n');
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3488kb
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: 3444kb
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: 3452kb
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:
16474230242881427288
result:
wrong answer 1st lines differ - expected: '17883317185357051350', found: '16474230242881427288'