QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#243959#7520. Monster GeneratorqwqwfWA 1ms3488kbC++144.2kb2023-11-08 19:42:052023-11-08 19:42:05

Judging History

你现在查看的是最新测评结果

  • [2023-11-08 19:42:05]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3488kb
  • [2023-11-08 19:42:05]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'