QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#243938#7520. Monster GeneratorqwqwfWA 1ms3612kbC++142.5kb2023-11-08 19:28:262023-11-08 19:28:26

Judging History

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

  • [2023-11-08 19:28:26]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3612kb
  • [2023-11-08 19:28:26]
  • 提交

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

详细

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'