QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#357279	#3276. 出题高手	Harry27182	15	113ms	13684kb	C++14	1.4kb	2024-03-18 19:55:09	2024-03-18 19:55:10

Judging History

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

[2024-03-18 19:55:10]
评测

测评结果：15
用时：113ms
内存：13684kb

查看

[2024-03-18 19:55:09]
提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{int x,y;}ans[100005],tr[400005];
int n,m,a[100005],sum[100005],l,r;
vector<pair<int,int> >v[100005];
bool operator <(node x,node y)
{
	if(x.y==0||y.y==0)return x.y==0;
	return x.x*y.y<x.y*y.x;
}
void cmax(node &x,node y){x=(x<y?y:x);}
int gcd(int x,int y){return (!y?x:gcd(y,x%y));}
void change(int k,int l,int r,int x,node v)
{
	if(l==r){cmax(tr[k],v);return;}
	int mid=(l+r)>>1;
	if(x<=mid)change(k<<1,l,mid,x,v);
	else change(k<<1|1,mid+1,r,x,v);
	tr[k]=tr[k<<1];cmax(tr[k],tr[k<<1|1]);
}
node query(int k,int l,int r,int x,int y)
{
	if(x<=l&&r<=y)return tr[k];
	int mid=(l+r)>>1;node res={0,0};
	if(x<=mid)cmax(res,query(k<<1,l,mid,x,y));
	if(y>mid)cmax(res,query(k<<1|1,mid+1,r,x,y));
	return res;
}
signed main()
{
	cin.tie(0)->sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i],sum[i]=sum[i-1]+a[i];
	cin>>m;
	for(int i=1;i<=m;i++)cin>>l>>r,v[l].emplace_back(make_pair(r,i));
	for(int i=n;i>=1;i--)
	{
		if(a[i]==0)continue;
		node mx={0,0};
		for(int j=i;j<=n;j++)
		{
			if((sum[j]-sum[i-1]>0)!=(a[i]>0))break;
			node now={(sum[j]-sum[i-1])*(sum[j]-sum[i-1]),j-i+1};
			if(mx<now)mx=now,change(1,1,n,j,now);
		}
		for(int j=0;j<v[i].size();j++)ans[v[i][j].second]=query(1,1,n,i,v[i][j].first);
	}
	for(int i=1;i<=m;i++)
	{
		int g=gcd(ans[i].x,ans[i].y);
		cout<<ans[i].x/g<<' '<<ans[i].y/g<<'\n';
	}
	return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0

Runtime Error

Test #1:

score: 5

Accepted

time: 29ms

memory: 13192kb

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:

54826875 11
14638276 7
1185921 1
81018001 24
6310144 3
12545764 5
3362000 1
23068809 8
23068809 8
12545764 5
1444908 1
5424241 3
1083603 1
2140369 1
2752281 2
3095072 1
3003289 2
4959529 2
17106496 13
4780232 1
89605156 31
8543929 4
129163225 48
5094049 2
68591524 23
8543929 4
35688676 11
3775249 1
...

result:

ok 200000 numbers

Test #2:

score: 0

Accepted

time: 25ms

memory: 13088kb

input:

2000
717 273 112 -879 -487 -164 -403 -895 391 721 223 895 -34 146 -779 -84 253 44 690 716 975 -625 844 731 204 457 -790 349 -739 610 -536 -561 721 -868 -967 68 729 878 672 -158 -395 -836 383 -634 -371 -262 -443 -123 -20 354 198 171 681 -390 -964 954 735 713 -904 -900 -522 561 -639 -86 326 -479 448 -...

output:

82773604 23
58201641 20
2289169 1
40500496 19
1849372 1
12759184 5
2896804 1
14775048 7
7636232 5
1806005 1
3179089 2
26388769 16
1638050 1
2778889 2
156275001 49
17181522 7
2289169 1
6817321 3
758912 1
40500496 19
4941729 2
8276763 5
5841889 3
3250809 2
1806005 1
2289169 1
156275001 49
9684544 5
25...

result:

ok 200000 numbers

Test #3:

score: -5

Runtime Error

input:

2000
-851 -108 -432 344 -251 251 529 923 363 -346 416 -296 -686 832 565 66 150 -492 70 0 -977 -275 -454 -409 -979 353 -511 -458 -403 632 250 -689 -15 773 664 -386 931 -866 436 -213 711 -961 662 -849 -286 -143 -7 -933 960 -523 135 -609 86 408 643 -147 437 411 -580 -184 735 -968 417 977 863 325 518 83...

output:

result:

Subtask #2:

score: 15

Accepted

Test #6:

score: 15

Accepted

time: 83ms

memory: 13592kb

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:

466344025 67

result:

ok 2 number(s): "466344025 67"

Test #7:

score: 0

Accepted

time: 94ms

memory: 13684kb

input:

100000
-387 -313 -47 -714 -74 239 8 591 541 -633 -660 981 -230 -148 -813 -802 -108 -543 -640 50 962 137 -972 -936 -975 885 793 -541 932 861 -348 885 -280 -977 -677 964 355 604 54 -977 -548 979 -516 136 437 -697 -23 -748 492 897 -538 785 617 -840 675 -978 307 -288 -493 682 678 -623 613 762 -622 -283 ...

output:

2417885584 385

result:

ok 2 number(s): "2417885584 385"

Test #8:

score: 0

Accepted

time: 81ms

memory: 11588kb

input:

100000
-127 303 92 -235 -794 293 -272 199 -175 693 -799 -750 -501 -283 -358 -657 -867 -152 -399 -299 530 -5 285 959 390 -928 617 -478 -889 -133 -492 -855 986 -664 -984 -690 887 -738 39 -570 -268 -767 640 883 711 -748 -75 426 -268 -541 -926 -792 902 214 561 -428 -285 781 -225 -299 -233 134 -896 569 -...

output:

202236841 30

result:

ok 2 number(s): "202236841 30"

Test #9:

score: 0

Accepted

time: 113ms

memory: 13636kb

input:

100000
-340 -696 48 -515 -584 -60 -888 257 214 -889 782 915 905 -964 -536 459 779 -519 -338 -867 622 -902 655 -153 600 -117 269 -887 -242 -985 -267 132 406 98 -368 400 -871 -908 -489 118 -140 -755 -869 -943 965 609 47 -748 194 -160 994 527 871 119 -891 580 -687 865 826 56 -978 -775 -47 792 313 -944 ...

output:

272184004 39

result:

ok 2 number(s): "272184004 39"

Test #10:

score: 0

Accepted

time: 101ms

memory: 13544kb

input:

100000
-736 -691 738 209 -411 -136 792 -110 -441 -753 254 744 -958 -317 312 856 245 995 912 87 -830 131 393 37 -400 934 279 -784 -308 618 -647 967 527 -162 -874 -770 188 -917 -855 772 482 -373 -749 -40 80 -459 710 -354 221 -343 -132 -947 -445 62 -744 851 848 554 -530 -892 -721 -910 -642 -138 -480 -7...

output:

393070276 51

result:

ok 2 number(s): "393070276 51"

Subtask #3:

score: 0

Wrong Answer

Test #11:

score: 0

Wrong Answer

time: 6ms

memory: 7520kb

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:

wrong answer Answer contains longer sequence [length = 2], but output contains 0 elements

Subtask #4:

score: 0

Runtime Error

Test #16:

score: 0

Runtime Error

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:

1352474176 205
13957947 4
67914081 16
33243858 7
10885778 3
27836176 7
50680161 11
235284921 74
106770889 25
2411809 2
2835045 1
14017536 5
134699236 43
286523329 74
28100601 11
17546888 5
23396569 6
80839443 25
4012009 3
2661336 1
42947912 11
3474284 1
61496964 19
3672245 1
6120676 3
7573504 3
1489...

result:

Subtask #5:

score: 0

Runtime Error

Test #31:

score: 0

Runtime Error

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...