QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #357284 | #3276. 出题高手 | Harry27182 | 0 | 88ms | 13908kb | C++14 | 1.4kb | 2024-03-18 19:56:57 | 2024-03-18 19:56:58 |
Judging History
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);
}
return 0;
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;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 21ms
memory: 13136kb
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:
result:
wrong answer Answer contains longer sequence [length = 200000], but output contains 0 elements
Subtask #2:
score: 0
Wrong Answer
Test #6:
score: 0
Wrong Answer
time: 85ms
memory: 13536kb
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:
result:
wrong answer Answer contains longer sequence [length = 2], but output contains 0 elements
Subtask #3:
score: 0
Wrong Answer
Test #11:
score: 0
Wrong Answer
time: 6ms
memory: 8028kb
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
Wrong Answer
Test #16:
score: 0
Wrong Answer
time: 88ms
memory: 13908kb
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:
result:
wrong answer Answer contains longer sequence [length = 10000], but output contains 0 elements
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...