QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#79494#3276. 出题高手tricyzhkx0 40ms11216kbC++141.6kb2023-02-20 10:05:222023-02-20 10:05:23

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-20 10:05:23]
  • 评测
  • 测评结果：0
  • 用时：40ms
  • 内存：11216kb
查看
  • [2023-02-20 10:05:22]
  • 提交

answer

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,a[500010],sum[500010],stk[500010];
template<typename T>
void upd(T &a,const T &b){a=max(a,b);}
struct Frac
{
	int a,b;// a^2/b
	Frac(int _a=0,int _b=0):a(_a),b(_b){}
	bool operator<(const Frac &x)const{return (ll)a*a*x.b<(ll)x.a*x.a*b;}
}maxn[500010],ans[300010];
struct Query
{
	int l,r,id;
	bool operator<(const Query &x)const{return l>x.l;}
}que[300010];
bool cmpl(Query a,Query b){return a.l>b.l;}
bool cmpr(Query a,Query b){return a.r<b.r;}
void update(int x,const Frac &y){for(int i=x;i<=n;i+=i&(-i)) upd(maxn[i],y);}
Frac query(int x)
{
	Frac ans(0,1);
	for(int i=x;i;i-=i&(-i)) upd(ans,maxn[i]);
	return ans;
}
int main()
{
	int q,tp=0;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
	cin>>q;
	for(int i=1;i<=q;i++) scanf("%d%d",&que[i].l,&que[i].r),que[i].id=i;
	fill(ans+1,ans+q+1,Frac(0,1));
	sort(que+1,que+q+1,cmpr);
	fill(maxn+1,maxn+n+1,Frac(0,1));
	for(int i=0,j=1;i<=n;i++)
	{
		while(tp && sum[stk[tp]]>=sum[i]) tp--;
		for(int j=1;j<=tp;j++) update(n-stk[j],Frac(sum[i]-sum[stk[j]],i-stk[j]));
		stk[++tp]=i;
		for(;j<=q && que[j].r==i;j++) upd(ans[que[j].id],query(n-que[j].l+1));
	}
	tp=0;
	sort(que+1,que+q+1,cmpl);
	fill(maxn+1,maxn+n+1,Frac(0,1));
	for(int i=n,j=1;i>=0;i--)
	{
		while(tp && sum[stk[tp]]>=sum[i]) tp--;
		for(int j=1;j<=tp;j++) update(stk[j],Frac(sum[stk[j]]-sum[i],stk[j]-i));
		stk[++tp]=i;
		for(;j<=q && que[j].l==i+1;j++) upd(ans[que[j].id],query(que[j].r));
	}
	for(int i=1;i<=q;i++)
	{
		ll a=(ll)ans[i].a*ans[i].a,b=ans[i].b,g=__gcd(a,b);
		printf("%lld %lld\n",a/g,b/g);
	}
	return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 9876kb

input:

2000
-113 314 -664 697 211 -199 -38 -190 8 -661 910 -811 -113 942 77 433 -261 -368 129 -525 968 -608 -21 38 -562 438 -935 -228 220 333 985 -430 916 586 764 476 794 664 383 503 206 -60 380 -130 -988 -904 -996 -304 -286 31 114 119 850 -942 714 -369 -842 250 -192 -462 -727 -427 -602 126 231 718 121 559...

output:

0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
...

result:

wrong answer 1st numbers differ - expected: '54826875', found: '0'

Subtask #2:

score: 0
Wrong Answer

Test #6:

score: 0
Wrong Answer
time: 35ms
memory: 10996kb

input:

100000
754 792 -680 426 425 347 481 -690 530 378 73 -907 -431 45 -530 -552 440 -890 -15 712 695 -679 -310 13 718 805 193 -291 -877 -74 -355 511 -679 -395 166 -710 -657 -19 874 26 832 507 854 -289 700 -404 472 -302 -977 8 -698 40 766 705 369 838 700 -964 552 -535 -75 -608 -181 -503 468 447 772 904 -2...

output:

0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
...

result:

wrong answer 1st numbers differ - expected: '466344025', found: '0'

Subtask #3:

score: 0
Runtime Error

Test #11:

score: 0
Runtime Error

input:

500000
794 -75 -596 -322 -945 -908 -609 -164 488 626 -877 -710 140 -120 -475 -837 738 669 634 -643 -682 667 816 -785 -608 -836 -860 -932 242 70 -620 268 -121 288 209 -392 732 750 558 -480 565 327 -217 -891 767 211 -690 -66 813 -889 952 615 432 19 411 800 678 718 522 422 940 -510 -544 449 -357 640 40...

output:

result:

Subtask #4:

score: 0
Wrong Answer

Test #16:

score: 0
Wrong Answer
time: 33ms
memory: 11216kb

input:

100000
-496 -233 354 -632 -196 177 -878 -255 -19 -636 685 -70 101 -975 -406 -988 -965 -205 563 -766 763 511 -116 -746 -129 14 106 928 -457 -257 -283 226 3 899 -359 -792 615 490 -57 986 -243 624 -239 931 -555 -821 -72 -611 -380 -397 248 -132 956 -195 -322 -231 319 -214 837 -379 -931 -301 -4 -673 280 ...

output:

0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
...

result:

wrong answer 1st numbers differ - expected: '1352474176', found: '0'

Subtask #5:

score: 0
Wrong Answer

Test #31:

score: 0
Wrong Answer
time: 40ms
memory: 10960kb

input:

100000
139 -485 -497 -818 254 169 -560 22 377 -67 -243 -75 743 -788 -676 -26 -775 371 576 -303 54 733 422 800 445 687 479 -16 -288 259 783 -586 912 616 439 -416 676 -555 172 659 501 -868 337 22 -60 260 603 -982 -149 466 769 -595 -117 949 -544 904 753 20 776 175 -888 937 -792 -647 -615 59 -298 452 -6...

output:

0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
...

result:

wrong answer 1st numbers differ - expected: '401594700', found: '0'
English 繁體中文 简体中文

Server Time: 2024-12-02 06:31:13 | OpenSource Project